Recommend sorted collection to search closest value left and right

Question

Is there ready data structure in .NET 3.5 to do the following

store values sorted by decimal key, dublicates allowed

get next value (enumerator) closest to given key left and right

An example:

car dealer has cars, client asks to find the most expensive car but cheaper than 1000$

Is there that much data that you can't sort the list when needed? You could just create a List based on price and sort it on demand. With some IComparable-magic you can even create a List and have it sorted on Price. — CodingBarfield, Feb 07 '11 at 09:20
@ Barfieldmv: quite a few data entries. I am just wondering if there is existing collection in the .NET to suit that. — Captain Comic, Feb 07 '11 at 09:24

score 5 · Accepted Answer · edited May 23 '17 at 11:45

5

You are looking for a binary tree allowing duplicate keys (aka multi-set). There is no such thing in the .NET library, but they are easy to implement (and freely available, eg here or here).

See also Are there any implementations of multiset for .Net?

edited May 23 '17 at 11:45

Community

1
1

answered Feb 07 '11 at 09:21

Daniel Gehriger

7,339
2
34
55

yes std::multiset is closest analog except it does not provide closestvalue search – Captain Comic Feb 07 '11 at 09:26
1

The elements are sorted according to the key, so (in C++), if you move the iterator to the left, you'll get the next lower key, and to the right, the next higher. – Daniel Gehriger Feb 07 '11 at 09:50

gor · Answer 2 · 2011-02-07T11:03:16.837

1

I recommend you to use SQLite in for such queries. And your query will be:

from car in cars where car.Price < 1000 
order by car.Price descending
select car

edited Feb 07 '11 at 11:03

answered Feb 07 '11 at 09:44

gor

11,498
5
36
42

score 1 · Answer 3 · answered Feb 07 '11 at 10:09

1

You just use List to store car price and sort it every time you add new car price.

List<int> PriceList= new List<int>();
PriceList.Sort();

answered Feb 07 '11 at 10:09

mirfan00

129
2
9

Sorting is not effective, a tree structure must be used to provide Log(N) search – Captain Comic Feb 07 '11 at 10:13
@CaptainComic Ancient comment, but wrong. You can do a binary search on any sorted list resulting in `O(log n)` lookup time. Usually even faster than a tree due to the memory layout (more chance of having the entire list available in the cache memory). The thing that's significantly slower in a list is modification. If you have to insert an item halfway to keep it sorted you'll have to move all items behind it, resulting in an `O(n)` insertion most of the time. If the item should be inserted at the end it's `O(log n)`, unless it has to resize the internal array in which case it's `O(n)` again. – Aidiakapi Aug 12 '14 at 17:47

score 1 · Answer 4 · answered Feb 08 '11 at 05:05

I know that you're looking for ready-made structures, but one option that might be worth exploring is a van Emde Boas Tree. This structure gives you lookup, find successor, find predecessor, and delete all in O(lg lg n), time, which is exponentially faster than a balanced search tree. I'm not familiar with any implementations of this structure in C#, but it's probably the asymptotically optimal way of solving your problem. If you're storing a large number of integers, it can also be very space-efficient.

Recommend sorted collection to search closest value left and right

4 Answers4