3 ms·
The code seems to "remove" items from the array by setting an empty string to them. But in all mainstream languages I know of, an empty string is also a valid s
by alkonaut 8y ago
The code seems to "remove" items from the array by setting an empty string to them. But in all mainstream languages I know of, an empty string is also a valid string. So the item isn't "removed" it's simply replaced by the empty string. Am I completely misunderstanding what the author is trying to do?
Edit: Thanks: I missed the passage about this being the first step of two, with the compaction coming later (that step isn't in the article at all).
- incompatible 8y ago"All solutions here work in place, using the tombstone technique to create a sparse array, then compacting it later. " It just looks like the compacting step, creating the final array without the empty strings, has been omitted.
- desdiv 8y agoHis goal is to get ["apple", "dog", "cat"] from ["apple", "dog", "apple", "cat", "apple"]. He does it in two steps[0]: Step ONE: Replace any duplicate values with the empty string (the tombstone) in the original array. (Going from ["apple", "dog", "apple", "cat", "apple"] to ["apple", "dog", "", "cat"]). Step TWO: Compact the original array by creating a new array out of all non-tombstone values. He shows 4 different algorithms for performing Step ONE. He shows 0 algorithms for performing Step TWO because it's trivial. [0]: >We’d like solutions that conserve time and space. All solutions here work in place, using the tombstone technique to create a sparse array, then compacting it later.
- Someone 8y agoThat means it removes empty strings from the input. If this were a library function, I don’t think that’s acceptable (rationale: if you want to remove all empty strings, but the library function doesn’t, you can easily correct that. If you want to keep the first empty string, but the library function removes it, calling the library function is as good as useless)
- jerf 8y agoOn the flip side, if we're going to be discussing libraries, remember that things like "Maybe<String>" aren't free. That "Maybe" wrapper in the general case has to expand the size of the underlying data structure to adjoin an additional element to it, and that's something else a library may want to think twice about. I say "in the general case" because in the specific case it is not always necessary. ISTR Rust implements a specialization on pointers where you can syntactically wrap an Option around something and it's smart enough to use the null pointer directly as the missing case under the hood. However, if you've got something like a plain ol' machine int, you have to expand it somehow to get an Option or Maybe, because the compiler is not entitled to remove even a single element out of those for its purposes. How acceptable it is depends on your ability to declare an in-range (for the data type) element as the "impossible" element. Being able to use an in-range element is more efficient, but less general. In this case, simply by declaration Ted says empty strings are not valid. The next time he does this, they may be, and the technique would have to be adapted to that. A library that uses some equivalent to Option or Maybe is a good safe default for a library, of course. Another safe default is to create a new array and return that, too. It's not that hard to end up in a place where the safe default library is not suitable, although nowadays it takes enough data to choke a horse to get there since our computers are so darned fast.
- DougBTX 8y ago> ISTR Rust implements a specialization on pointers Yes, and NonZeroU8 for Option<NonZeroU8> and friends: https://doc.rust-lang.org/std/num/struct.NonZeroU8.html https://doc.rust-lang.org/std/num/struct.NonZeroU8.html