genericlemon24

Non-paywalled versions:

http://web.archive.org/web/20170913234634/https://medium.com...

http://webcache.googleusercontent.com/search?q=cache:https:/...

https://docs.python.org/3/library/bisect.html

Glad to hear that :D One of my main goals was to show the entire progression of how I approached the problem, instead of just saying "here's the final result".

I have another article that covers profiling in more detail, you might find it useful: https://death.andgravity.com/fast-conway-cubes#intro-to-prof...

Note that besides the cProfile text output, there are better, graphical tools for profiling; I've personally used pyflame+flamegraph.pl, and tuna.

You can, see the next paragraph, "also narrow down around the estimated position iteratively..."

I gave up because I was too lazy to think how to do the "precompute the maximum +/- error bounds" jiggawatts mentions in https://news.ycombinator.com/item?id=34021826

I did try mmap, both with the plaintext binary search, and with the binary file (you can find a note about it in the HTML source :)

I ended up not mentioning it because for some reason, it was ~twice as slow on my mac... I'm now curious to try it on a decent Linux machine.

(replying with more details, because I think it's pretty cool, and I'll definitely try this out)

The linked item is to https://blog.mro.name/2022/08/pwned-diy/, where the author converts the passwords list to a CDB (Constant DataBase) file, a simple, fast lookup database format created by D. J. Bernstein.

https://cr.yp.to/cdb.html

https://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html

Hey, I didn't know about this command, neat!

On my laptop, look `time`s at ~10 ms (for comparison, the Python "binary search" script `time`s at ~50 ms).

Not yet, I might give it a try.

You can, Scott Helme wrote some articles about this (I mention them at the end of my article):

* https://scotthelme.co.uk/when-pwned-passwords-bloom/

* https://scotthelme.co.uk/sketchy-pwned-passwords/ – here he uses a count-min sketch to also store the frequency

I actually did try this, but I got impatient and stopped it after 30 minutes or so, and a ~20G database file.

For some reason, after that, `ls` in that directory (or even shell completion) would freeze the shell entirely, even after reboot. I eventually managed to delete the file with `rm db.sqlite` (no completion allowed), but even that took like 2 minutes.

I might try again with WAL enabled (based on my shell history, I also deleted a -journal file).

(author here) Hey, that's actually a great idea. I remember reading about a fast grep or wc implementation that did parallel reads.

Off the top of my head, I don't really know how to do that (aside from the naive way of using threads), I'm guessing readv[1] might be be useful? Will definitely look into it.

[1] https://linux.die.net/man/2/readv

I mention PCRE in passing at the end of the article, but I didn't know about (?(DEFINE)...); that's very, very cool!

An infinity! https://xkcd.com/1313/

Thank you!

For one, it can output more than one flavor of SQL: https://pypika.readthedocs.io/en/latest/3_advanced.html#hand...

Since SQL is ever-so-slightly different across databases, I imagine trying to cover all of them as a single dev is a nightmare (especially if that's not the problem you're trying to solve).

I wrote my own query builder because I know for sure I'm only targeting SQLite. The second I need my feed reader library to work with another database engine I'm dumping my own for something more serious – either a full blown database abstraction layer like SQLAlchemy or Peewee (likely without the ORM part), or something simpler like PyPika or python-sql.[1]

[1]: I talk more about them here: https://death.andgravity.com/own-query-builder#sqlbuilder-py...

Yup, after my own initial research I found it as well, and I like it a lot. I talk more about it here: https://death.andgravity.com/own-query-builder#sqlbuilder-py...

Hey, thanks for that!

It's magic when it works but it suffers from the drawbacks noted elsewhere in the thread about traditional ORMS...

(Not that there are lots of other devs on my project at the moment, but)

I am managing this by aggressively limiting the size / features of my query builder, so it's (relatively) easy to understand just by looking at the code.

If it ever passes that point, it's probably time to switch to a "real" query builder / ORM.

Hey, this has roughly the same philosophy as mine, I might add it to my survey: https://death.andgravity.com/own-query-builder#sqlbuilder-mi...

Glad you liked it!

That's what the fancier __init__() at the end of the article[1] is for :)

Here's the tl;dr of a real-world example[2]:

    query = Query().SELECT(...).WHERE(...)
    for subtags in tags:
        tag_query = BaseQuery({'(': [], ')': ['']}, {'(': 'OR'})
        tag_add = partial(tag_query.add, '(')
        for subtag in subtags:
            tag_add(subtag)
        query.WHERE(str(tag_query))

    for subtags in tags:
        tag_query = QList('OR')
        for subtag in subtags:
            tag_query.append(subtag)
        query.WHERE(str(tag_query))

[2] https://github.com/lemon24/reader/blob/10ccabb9186f531da04db...

It's not either-or; I'm using the query builder to build _parametrized_ queries.

Here are two examples:

https://death.andgravity.com/query-builder-why#introspection https://github.com/lemon24/reader/blob/10ccabb9186f531da04db...

What does `query.SELECT("one")` on its own represent?

data['SELECT'].append('one')

I'm intentionally trying to not depart too much from SQL / list-of-strings-for-each-clause model, since I'd have to invent/learn another one.

For a full-blown query builder, I agree Table("table").select("one") is better.

I cover this solution here: https://death.andgravity.com/own-query-builder#jinjasql-sqlp...

I am using exactly that; the query builder goes on top of it :)

Someone on Reddit suggested stored procedures, which seems like a good alternative.

Alas, SQLite doesn't have them, so query building it is.

I wrote an entire article about why I didn't do that: https://death.andgravity.com/own-query-builder#sqlalchemy-co...

In general, SQLAlchemy is an excellent choice; in my specific case (single dev with limited time), the overhead would be too much (even with my previous experience with it).

Sometimes you need dynamic SQL, because the DB doesn't have stored procedures you can use for the same purpose (e.g. SQLite).

I talk more about this use case here: https://death.andgravity.com/query-builder-why#the-problem

In that sense, if anything this is a downgrade from regular SQL.

It likely is.

Ideally, instead of dynamically building queries, one would use stored procedures.

I'm using this with SQLite, which doesn't have stored procedures, so it's an acceptable downgrade for me. Appending strings to lists gets messy quickly, example: https://death.andgravity.com/query-builder-why#preventing-co...

(author here)

Yup, good thing to note, thank you!

I've kinda assumed everyone knows about the named parameters some bindings offer, but that's probably not true. Will add a disclaimer.

In the previous articles, I do talk about how this is an upgrade from plain SQL, not from regular full-blown query builders / ORMs.