search

elliotchance / orderedmap

🔃 An ordered map in Go with amortized O(1) for Set, Get, Delete and Len.
MIT License
763 stars 62 forks source link

Why list.List? #3

Open funny-falcon opened 4 years ago

funny-falcon commented 4 years ago

If you wanted to build “high performance” thing, then why you didn’t implement list by hands? Why you decided to pay overhead of list.Element?

elliotchance commented 4 years ago

This is the first time I've used the container/list package, what is the overhead you're referring to?

guoruibiao commented 4 years ago

it seems that orderedmap is just the wrapper of list.[Element+List]

algobot76 commented 4 years ago

The linked list is used to record the insertion order. This is how OrderedDict is implemented in Python as well (see: https://stackoverflow.com/questions/34496582/is-ordereddict-a-tree).

algobot76 commented 4 years ago

Also: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

funny-falcon commented 4 years ago

This is the first time I've used the container/list package, what is the overhead you're referring to?

Separate allocation of list.Element and orderedMapElement. Excess interface pointer from list.Element to orderedMapElement. Excess interface casting for taking orderedMapElement from list.Element.Value.

I'd rather call your implementation “naive” or “lazy” (in term “I was lazy to do low level code by hand, so I took standard library despite it is not for high performance but for lazy programmers”).

funny-falcon commented 4 years ago

I mean, it is not bad to be lazy. Being lazy helps to do less mistakes, and to write more code that has business value.

But “high performance” code in Go could not be written in lazy way.

Just don't call it “high performance”.

elliotchance commented 4 years ago

I take your point. However “high performance” is a relative term, not a quantitative one. If it bothers you, then I’m happy to review a PR with improvements.

rocaltair commented 3 years ago

How can you say it is a orderedmap? with O(1) ?

elliotchance commented 3 years ago

How can you say it is a orderedmap?

It will maintain the keys in the order they were inserted. This is something Go does not do natively with maps.

with O(1) ?

This means operations (Len, Get, Set etc) takes about the same amount of time, regardless of the size of the underlying orderedmap.