3 ms·
At least he mentions the name of his technique: setting tombstones. Of course it's highly problematic not to explain why he choose "" as tombstone. It looks li
by rurban 8y ago
At least he mentions the name of his technique: setting tombstones.
Of course it's highly problematic not to explain why he choose "" as tombstone. It looks like a legal array value to me, so offline compaction will have a hard time to separate a tombstone from an empty string. Without documentation and assertions that "" is not a legal value on insert, certainly a bug.
But he fails to list other common useful techniques, without tombstones:
1) if it's the first index to be removed, just advance the array pointer by one, and keep the original pointer separate for the final free call. very useful for strings, cutting off prefixes.
2) sparse arrays: he mentioned it, but he doesn't use it in his code. Just leave out the hole. very useful for matrixes.
3) temporary hashes. if the array is long (like >256), use a temp. hash to find duplicates.
4) copy to new array, leaving out the duplicates. mostly together with a temp. hash. but for short arrays a linear search is also doable. he showed the linear search, but only with tombstones. This is the functional approach, always copy instead of destructive modifications. This is done in offline compaction.
5) for large arrays use a bloom filter to find dups. can be tuned to the best percentage. (This is what I used in my file deduper, which turned out better than normal hashes)
- viraptor 8y ago> not to explain why he choose "" as tombstone Because his "neutral pseudocode" (go) doesn't allow setting the string entries in an array to nil. You have to have some value, so commonly you'd use "".
- LordHeini 8y agoBut one can not add an empty string to the array which is an obvious bug. There are slices in go which should be used in this case.
- viraptor 8y agoIt's a toy example in a semi-funny (or trying) post. Did you really expect handling of all the edge cases?
- rurban 8y agoNo because it's Ted Unangst writing about "Removing Array Duplicates", the guy who added string arguments being comma-splitted at run-time instead of using safe and fast bitmasks to new OpenBSD API's. So we know already that he has no idea what he's doing, and shouldn't be let to any important API in serious projects. But he writes like he has an idea what he's doing, so I had to explain the common cases for this problem. Using tombstones is a special case and you need to be lucky to have such a special illegal value available. Most cases don't allow it, esp. in strongly typed languages.