3 ms·

His 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

by desdiv 7y ago

His 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 7y ago
That 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 7y ago
  On 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 7y 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

by desdiv 7y ago

Someone 7y ago

That 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 7y ago
On 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 7y 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