Эффективный способ перебора массива для определенного члена

В моем последнем проекте я обнаружил, что перебираю множество массивов или списков строк, чтобы найти определенную строку внутри.Эффективный способ перебора массива для определенного члена

Я должен спросить, есть ли способ меньше, чем O(n), чтобы найти конкретный элемент внутри массива?

O(n) решение в C# (рассмотреть нет дубликатов):

foreach(string st in Arr) 
{ 
    if (st=="Hello") 
    { 
     Console.WriteLine("Hey!"); 
     break; 
    } 
}

EDIT: Я не задавал мой вопрос совсем верно. Я хочу изменить члена, которого я хочу найти, и не только искать его. Так что мой сниппет меняется:

foreach(string st in Arr) 
{ 
    if (st=="Hello") 
    { 
     st="Changed"; 
     break; 
    } 
}

Можете ли вы как-то добраться до O(logn)? Если да, можете ли вы объяснить, как это делается и как оно более эффективно, чем мое решение. Спасибо за любой свет в этом отношении!

источник

2015-06-30 Oranges

Вы собираетесь сделать это один раз или много раз? Для одного доступа к массиву или списка O (n) является вашим лучшим, но если вы делаете это много раз, вам может быть лучше помещать их в другую структуру (например, сначала сортировать их, помещать в HashSet и т. Д. – Chris

You может использовать ['SortedList'] (https://msdn.microsoft.com/en-us/library/system.collections.sortedlist (v = vs.110) .aspx) – Itay

Я не уверен, что порядок операций но, возможно, используя что-то вроде «Arr.Find» (x => x == «Hey»), 'может быть более эффективным. Я не уверен, как LINQ обрабатывает поиск через массив. – Melvin

есть ли какой-либо путь меньше, чем O (n), чтобы найти конкретный элемент внутри массива?

Если у вас есть набор строк, без каких-либо отношении дублей, и вроде это не вопрос, вы должны использовать HashSet<T>, где с нормальным распределением, вы должны быть в O(1) для поисков:

var hashSet = new HashSet<string> { "A", "B", "C" }; 
if (hashSet.Contains("A")) 
{ 
    Console.WriteLine("hey"); 
}

Если вам нужно больше, чем поиск, например доступ к члену по определенному индексу, то HashSet<T> не должен быть вашим выбором. Вам нужно точно указать, что вы собираетесь делать с коллекцией, если вы хотите получить более подробный ответ.

источник

2015-06-30 12:42:44

вы не можете вставить дубликат в HashSet, но можете в массиве – dotctor

@dotctor Где он сказал что-нибудь о дубликатах? Хотя я добавил это как комментарий. –

Это теряет некоторые аспекты массива или списка, хотя для одного заказа. Это может быть не важно, но вы должны действительно указать, что может быть потеряно при изменении типа данных. – Chris

В Копенгагенском университете есть проект под названием "C5 Generic Collection Library". Они внедрили расширенный набор классов сбора, которые могут вам помочь, такие как HashSet, который позволяет дубликаты, называемые hashbag, и у них есть список хеш-индексированных массивов, который может оказаться полезным ...

источник

2015-06-30 12:48:25 AnthonyLambert

Эффективный способ перебора массива для определенного члена

ответ

Смежные вопросы