Что такое эффективный способ фильтрации массива

Question

Я программирую c на linux, и у меня есть большой целочисленный массив, как его фильтровать, скажем, найти значения, которые соответствуют некоторому условию, например. value> 1789 & & Значение < 2031. Каков эффективный способ сделать это, нужно ли сначала отсортировать этот массив?

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

Answer 1

Сортировать массив первым. Затем по каждому запросу выполняются 2 бинарных поиска. Я предполагаю, что запросы будут как -

Find integers x such that a < x < b 

Первый бинарный поиск будет найти индекс i элемента таким образом, что Array[i-1] <= a < Array[i] и второго двоичного поиска найдет индекс j таким образом, что Array[j] < b <= Array[j+1].Тогда ваш желаемый диапазон будет [i, j].

сложность этого алгоритма является O(NlogN) в предварительной обработке и O(N) на запрос, если вы хотите перебрать все элементы и O(logN) на запрос, если вы просто хотите, чтобы подсчитать количество отфильтрованного элемента.

Сообщите мне, если вам нужна помощь в реализации двоичного поиска на C. Существует функция библиотеки с именем binary_search() в C и lower_bound() и upper_bound() в C++ STL.

Answer 2

Чтобы отфильтровать массив, вам нужно будет просмотреть каждый элемент один раз. Нет необходимости смотреть на какой-либо элемент больше, чем один раз, поэтому простой линейный поиск массива для элементов, соответствующих вашим критериям, будет таким же эффективным, как вы можете получить.

Сортировка массива в конечном итоге будет рассматривать некоторые элементы более одного раза, что не обязательно для вашей цели.

Answer 3

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

Answer 4

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

Answer 5

Если вы можете зарезервировать еще немного памяти, вы можете сканировать свой массив один раз, получить индексы совпадающих значений и сохранить их в другом массиве. Этот новый массив будет значительно короче, поскольку он имеет только индексы значений, которые соответствуют определенному шаблону! Что-то вроде этого

int original_array[SOME_SIZE]; 
int new_array[LESS_THAN_SOME__SIZE]; 

for (int i=0,j=0; i<SOME_SIZE; i++) 
{ 
    if (original_array[i]> LOWER_LIMIT && original_array[i]< HIGHER_LIMIT) 
    { 
     new_array[j++] = i; 
    } 
} 

Вы должны делать выше один раз и образуют теперь,

for (int i=0; i< LESS_THAN_SOME_SIZE; i++) 
{ 
    if (original_array[new_array[i]]> LOWER_LIMIT && original_array[new_array[i]]< HIGHER_LIMIT) 
    { 
     printf("Success! Found Value %d\n", original_array[new_array[i]]) 
    } 
} 

Так за счет некоторой памяти, вы можете сэкономить значительное количество времени. Даже если вы потратите некоторое время на сортировку, вы должны разобрать отсортированный массив каждый раз. Этот метод минимизирует длину массива, а также время сортировки (по стоимости дополнительной памяти, конечно :))

Answer 6

Попробуйте эту библиотеку: http://code.google.com/p/boolinq/

Это итератор на основе и так же быстро, как может быть, нет никаких накладных расходов. Но для этого нужен стандарт C++ 11. YOR код будет записан в декларативной-полосная:

int arr[] = {1,2,3,4,5,6,7,8,9}; 

auto items = boolinq::from(arr).where([](int a){return a>3 && a<6;}); 
while (!items.empty()) 
{ 
    int item = items.front(); 
    ... 
} 

быстрее, чем итератора на основе сканирования может быть только многопотоковые отсканировать ...