C # Быстрый способ найти значение в массиве неровной

Question

У меня есть зубчатый массив String[][].Теперь мне нужно найти массив с определенным значением в String[n][0], что у меня есть простой момент

foreach foo in bar{
 if(foo[0]==needle){
  return foo;
 }
}

Как вы можете видеть, это очень медленно по очевидным причинам.Я новичок в C # и только что увидел indexOf, но как я могу использовать indexOf в зубчатом массиве?

Другой способ, о котором я говорил, это Сортировка массива по String[n][0], переход к записи в серединепроверьте, больше или больше мое значение, прыгните в половину верхней / нижней области и т. д., возможно, в 3 или 4 раза, чтобы я мог быстрее найти запись.

Так какой же самый быстрый способ полученияМассив в зубчатом массиве, где я знаю только [][0]?

Answer 1

Я бы использовал Dictionary<int, int[]>, где ключ - это первый элемент массива. Словари имеют постоянный доступ по времени и очень быстры для произвольного доступа, если все данные помещаются в память.

Answer 2

Возможно, вместо зубчатого массива вам лучше подойдет словарь, в котором ключ является первым элементом каждого из ваших массивов. Поскольку словари являются хеш-таблицами, поиск должен быть быстрым.

// Some test data.    
var dictionary = new Dictionary<string, string[]>
{
    { "foo1", new string[] { "foo1", "bar1" }},
    { "foo2", new string[] { "foo2", "bleh" }},
    { "foo3", new string[] { "foo3", "bar3", "hello", "world" }},
    { "foo4", new string[] { "foo4",  }},
    { "foo5", new string[] { "foo5", "bar5", "test" }},
};

string[] item = dictionary["foo3"]; // Fast look up.

Answer 3

Ну, вы ищете значение, которое может быть на array[i][0] для каждого i от 0 до n, верно? Тогда это не имеет ничего общего с зубчатыми массивами, но с поиском значения в коллекции (которая в вашем случае является коллекцией {array[i][0], for each 0 <= i < n )

Если вы собираетесь искать только один раз, то лучшее, что можно сделать, - это ваше собственное решение, работающее по линейному времени: O(n)

Если вы собираетесь искать много раз (без изменений array[i][0] для любого i), то вы можете отсортировать массив по String[n][0] и выполнить «двоичный поиск», который в точности соответствует описанному вами алгоритму. Сортировка займет O(n lgn) времени. Но каждый поиск будет очень быстрым O(lg n).