Say I have a bunch of meaningless hashes. The only thing I can do with these hashes is subtract them, which spits out a float. A small float means the hashes are very similar, a large float means the hashes are very different. Given a hash as input, how can I efficiently find similar hashes?
I could've sworn I've heard of a "distance tree" data structure, but I can't find any info about it
Intuition says iterate over the million hashes and keep track of every one that fits the criteria. But I suspect there's something fun you could do with a fully connected weighted graph.
Actually, let me move the goal posts a bit. Instead of finding all hashes that are similar to one specific x, I want to do that for every single hash in my data set. Basically cluster the whole data set into groups of similar hashes
@Aran-Fey Then have the sorted hashes and an inverted mapping of that, so hash => index. Given a hash, lookup the index in the sorted hashes; then use binary search to find the furthest hash.
If you want to cluster by similarity (as in DBSCAN or similar), you can move a window over the sorted hashes to check whether the next is still close enough to the pivot.
For some background info, my inputs are actually images. I create a list of all images on my PC, and then I want to find images that are similar to each other
@MisterMiyagi That won't work properly though. Sorting arranges the hashes in a 1-dimensional way, but I very much doubt that they're actually 1-dimensional
@NordineLotfi Yes, x - y returns the hamming distance between x and y. I still need a way to efficiently find all my ys though
the y in this case is "another image" in your dataset right? so, just make a for loop that goes through every image, and compare one to every other one using hamming distance hashing.
@roganjosh Not sure tbh. I know it converts the image to greyscale and then looks for "interesting" points in the image. This is resistant to rotation and scaling, but color inversion? Dunno
hmm, true. I guess you could do it using multiprocessing or multithreading (won't give too much as a speed up compared to the former) but I guess it's out of the question, maybe
@MisterMiyagi Yeah. If I understand the algorithm correctly, x - y returns the bitwise hamming distance, and the hashes are 8 bytes long per default, so... that makes the hashes effectively 64-dimensional?
@Aran-Fey I think there a way to do that without comparing each file to every other one. One way would be to just get the hash of each files, then only compare each hash to the file to get the percentage of similarity. There is some existing hamming distance based hashes algorithm that do this iirc. I played around with one like that one at least
this would be faster since on the second pass, you would just compare a small string, being the hash, to each file
There might be a formal term for this kind of property. If you imagine that each image is a point in space, and a straight line drawn between two points has a length corresponding to the image's bitwise hamming distance... x-z <= (x-y) + (y-z) holds true as long as the shortest distance between two points is a line
@Aran-Fey it means exactly what it means :) this is mostly dependent on a specific hashing algorithm I found once, but I need to remember the name of the project
If the problem is isomorphic to this kind of geometric representation, then you may be able to make use of data structures that work well on spatial data. For example an octree.
@Kevin I think x-z <= (x-y) + (y-z) does indeed hold true, but that thing you said about the shortest distance sounds like a red herring. Because hamming distance is essentially traveling across the axes, right? We're not taking the direct route from x to y
it probably doesn't always travel across the axis though. It's highly dependent on what we're comparing here. For example, most of the perceptual hashing algorithm use the binary representation of the "hashes", then use their hamming distance to say "okay, they are X time far from each other", or I guess the word "similar" work here too
you could implement your own way that use the hamming distance of some other properties of your data, which doesn't need to be binary, from the hashes, or etc
@roganjosh on top of a secret montain?
@Aran-Fey anyway, here an example of the algorithm that I can't remember the name of: lvngd.com/blog/…
We know that I have a "prototyping cave", which I imagine is a literal cave. Maybe with a stalagmite sanded flat into a primitive work surface.
Logically, the pondering area should be near the prototyping cave. Likely a place of undisturbed wilderness. A forest, or perhaps a rocky plateau. It would be nice if it was picturesque, but it doesn't have to be.
hashes = range(10)
max_difference = 3
# An example of a valid result
result = [[0, 1, 2, 3], [4, 5, 6, 7, 8, 9]]
for group in result:
assert max(group) - min(group) < max_difference * 2
"Forgot" is perhaps not the right word. If I say "the grocery store doesn't have coconuts", it would not necessarily be accurate to say "you forgot to fly to hawaii and visit a coconut grove"
I may have considered the possibility of flying to Hawaii the entire time I was searching fruitlessly through the grocery store. But alas, my lunch break is 60 minutes long and a flight to Hawaii is about 11 hours. So whether I remember Hawaii or not, my lunch will have no coconut.
@0x263A My pleasure! Larkin Poe are pretty special. Rebecca has an incredibly powerful & expressive voice. She's an excellent guitarist, but she's also an award-winning mandolin player. And of course Megan is the Slide Queen. :)
Speaking of mandolin, check out this recent performance of Whitewater, featuring bluegrass royalty. I love how Bela & Sam watch Sierra's fingers as they dance over the fretboard.
I wager that the original author had a regex with backslashes in it, and he knew it was broken because he had too many backslashes, or not enough.
Maybe he wrote .replace("\\\\", "\\") in the hopes this would fix everything. When it didn't, he changed it to .replace("\\", "\\"), knowing it was a no-op. Better to keep the general structure around for his next crack at the problem
@KarlKnechtel it's a snippet of what is running in production in this company right now. The context: get the list of 5-tuples that represent regex rules with certain associated values, keep the regex rule and one of the values, but gather them in reverse order
@vaultah mm. not sure how someone comes up with something that convoluted; I assume it's a multi-step process of repeatedly missing the obvious
>Better to keep the general structure around for his next crack at the problem No; better to actually understand how the system works and create strings that don't require a patch on the end.
that also doesn't justify the useless list wrapping and unwrapping, or the use of map (perhaps repeatedly adapted from a very old codebase?)
I've definitely used things like list(map(str, x)) or sum(map(len, x)) but when you have to write the lambda anyway.... ew
(map is also nice for the implicit zipping, sometimes)
(but mainly I like it because a list comprehension can't be eta-reduced)
@wjandrea I should put it here instead instead of cluttering the comments.
Most people who ask about "iterables" don't seem to realize that it doesn't mean the same thing as "sequences". In both of these questions, the example is constructed with a list, even. It's not that hard to create a non-indexable iterable for the purpose of a MRE; a file open for reading works, for example.
in more extreme cases, I've seen questions un-duped or argued about because of an entirely-meaningless-in-context distinction between lists and tuples.
@KarlKnechtel So what's the problem? Any solution that will work for any iterable will work for a list. If OP's confused, it's beside the point.
What I would do is put a comment under the question saying, "You said iterable, but you put a list, and lists actually support more solutions since they're sequences too. See How to iterate over a list in chunks."
And for the other one, "You said iterator, but you put a list, which isn't an iterator, though you can get an iterator out of it by calling iter() on it. As well, lists support more solutions since they're sequences too. See How to iterate over a list in chunks."
small rant: I have a policy of not directly answering fizzbuzz-level questions, but instead working through them in the comments - for the reason that, if the asker cannot solve a fizzbuzz-level question independently, why should I expect anything I write for an answer to be comprehensible?
larger rant: there are people who have answered thousands of questions on Stack Overflow, with accounts older than mine, who nevertheless don't seem to understand the most basic things about the site policy (not answering dupes and typos).