Duplicated functions not reported?

Stefan Koch via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Sun Apr 16 10:34:06 PDT 2017


On Sunday, 16 April 2017 at 17:10:14 UTC, Temtaime wrote:
> On Sunday, 16 April 2017 at 15:54:16 UTC, Stefan Koch wrote:
>> On Sunday, 16 April 2017 at 10:56:37 UTC, Era Scarecrow wrote:
>>> On Saturday, 15 April 2017 at 11:10:01 UTC, Stefan Koch wrote:
>>>> It would requires an O(n^2) check per declaration.
>>>> Even it is never used.
>>>> which would make imports that much more expensive.
>>>
>>>  Seems wrong to me...
>>>
>>>  If you made a list/array of all the functions (based purely 
>>> on signatures) then sorted them, then any duplicates would be 
>>> adjacent. Scanning that list would be O(n-1).
>>>
>>>  This assumes it's done after all functions are scanned and 
>>> identified, doing it earlier is a waste of time and energy.
>>
>>
>> sorting has O(n^2) worst case complexity.
>> Therefore totaling to O(n^2) worst case again.
>
> Why this difficulty ?
> Function[args][name] funcs;
>
> AA lookup is O(1).

AA lookup is _NOT_ O(1).
Worst case is O(n).


More information about the Digitalmars-d-learn mailing list