2

Here is the situation.

I have some objects that contain:

  • a starting long
  • an ending long
  • a string code

These objects longs are sequential. For example:

var obj1 = new {From = 0, To = 16777215, Code = "aaa"};
var obj2 = new {From = 16777216, To = 16777471, Code = "bbb"};

there are almost 150.000 objects like this.

For the moment I store everything in a SQL table.

The issue is I need to search from this list. For example, I need to look for the object with the number 16777470, which will be the object 2 "bbb".

Question : Is there an efficient way to store such an amount of objects in memory and being able to seek for elements in it, having a long and looking for the closest element ?

TaW
  • 53,122
  • 8
  • 69
  • 111
Tom741
  • 75
  • 1
  • 6
  • 4
    On a sorted list, Binary search can work. – Eser Aug 14 '15 at 12:06
  • 1
    Even if the objects average 50 bytes, that's less than 8MB total: would fit in the cache of many contemporary CPUs. Ie. not huge. – Richard Aug 14 '15 at 12:13
  • 1
    And it needs to be necessary on memory? because there're efficient ways to do that on SQL. – JuanK Aug 14 '15 at 12:16
  • It is already in SQL at the moment, but I'm afraid of it because this lookup will happened thousands times per minutes, I don't want to overload the database that is already highly solicited :). – Tom741 Aug 14 '15 at 12:23

2 Answers2

1

If the objects are sequential then you only need to store the 'from' number. 

var obj1 = new {From = 0, Code = "aaa"};
var obj2 = new {From = 16777216, Code = "bbb"};

This will save memory.

Then, if all the objects are in an ordered list a binary chop should address the efficient search.

The main performance hit may well be in setting up the lists in the fist place, so I think the suggestion to stay with an SQL database may be wise.

Peter Smith
  • 5,528
  • 8
  • 51
  • 77
0

I'm not sure from a memory efficiency point of view.

Thinking: You certainly don't want to search the entire list either, so some kind of secondary structure may be required (some kind of index or lookup????).

Anyway I stumbled across this: How to get the closest number from a List<int> with LINQ?

Suspect this method might be a bit processor intensive, as it doesn't have a secondary index.

Hope this helps.

Community
  • 1
  • 1
Philip Johnson
  • 1,091
  • 10
  • 24