Suggestion: Operator `in` for slices
Ola Fosheim Grøstad
ola.fosheim.grostad at gmail.com
Wed Dec 22 04:46:27 UTC 2021
On Tuesday, 21 December 2021 at 17:02:22 UTC, Steven
Schveighoffer wrote:
> On 12/19/21 2:34 PM, Ola Fosheim Grøstad wrote:
>> On Sunday, 19 December 2021 at 18:36:12 UTC, Steven
>> Schveighoffer wrote:
>>> That is what we claim (and what hash algorithms in general
>>> claim). amortized O(1) lookups and inserts.
>>
>> Yes, if you don't shrink.
>>
>> You need to prove that the claim holds for all possible
>> orderings of inserts, deletions and lookups.
>>
>> So you need to prove that you always do O(N) operations
>> between rehashing, so you get O(N) operations of complexity
>> O(1) + one rehash of complexity O(N) = O(N).
>
> Please see existing research, this is not a new concept.
What do you mean by research, this is a trivial topic. In order
to get O(1) amortised you have to delay shrinkage, you must prove
that any possible sequence does not reallocate more frequently
than N operations.
More information about the Digitalmars-d
mailing list