Задачка для программистов. Какой будет верный алгоритм

Новый комментарий
 

Есть двумерный динамический массив:

arr[][2];

В первой ячейке элемента массива номер параметра (уникальное значение), во второй ячейке тру или фолс (1 или 0)

Значения в массиве меняются по внешней команде. (Передается номер и значение)

Пример заполненного массива:

arr[1] = {123,true};

arr[2] = {200,false};

arr[3] = {81,true};

...

arr[20000] = {91,false};


Приходит задание: в параметре с номером 91 значение сделать фолс.

Какой стандартный алгоритм: Берем цикл, перебираем все ячейки пока не найдем параметр равный 91 и потом меняем значение.  (А если значение не нашли, то возвращаем еррор)


Можно ли как-то избавиться от постоянного перебора элементов массива?


(Есть дурацкий вариант: например создать массив из млрд элементов, где номер переменной будет такой же как номер элемента массива. Если приходит команда поменять переменную с номером 1000, то она находится в arr[1000]. Но насколько я понимаю, такой массив будет резервировать под себя память.) 

 

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

Может быть, сохранить данные в отсортированном массиве и пользоваться бинарным поиском.

Может быть, кэш сделать на десяток последних индексов. 

Все зависит от конкретной задачи.

 
Sergey Likho:

Можно ли как-то избавиться от постоянного перебора элементов массива?

В худшем случае можно свести к бинарному поиску.

В лучшем в прямой индексации. какое максимальное и минимальное значения параметра?

 

После предложения TheXpert'a - добавить нечего.

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

 
Верный ответ: "Какой бюджет у заказчика?"
 
Renat Akhtyamov:

первый массив - номера параметров с true, второй массив - false

int tru[], int fals[];

А вдруг надо будет переключить? Все равно придется искать. Но тем не менее, уже лучше - в два раза меньше искать.

 
Dmitry Fedoseev:

А вдруг надо будет переключить? Все равно придется искать. Но тем не менее, уже лучше - в два раза меньше искать.

а можно вообще - если в массиве int tru[] не найден, то по умолчанию - false
 
Renat Akhtyamov:
а можно вообще - если в массиве int tru[] не найден, то по умолчанию - false

Да. Упрощается поиск. Но надо знать задачу, может и нет.

 
Sergey Likho:

Есть двумерный динамический массив:

В первой ячейке элемента массива номер параметра (уникальное значение), во второй ячейке тру или фолс (1 или 0)

Это не двумерный массив, а одномерный массив с элементами - структурами. Коль скоро номер параметра уникален, то элементов столько же, сколько разных номеров. А не миллиард.

1. Этот массив можно вести, вставляя новые элементы в нужное место, а не просто добавлять элементы в конец. Тогда он будет упорядочен по номеру параметра, и будет работать двоичный поиск, очень быстрый.

2. Можно вместо упорядочивания массива поддерживать, как уже сказали, индекс по номеру параметра. Посмотрите, как в СУБД адресуются строки таблиц, номер параметра у Вас будет первичным ключом. Только если эти номера расположены неплотно, в самом индексе придется опять искать методом половинного деления.

Есть еще множество эффективных способов, но нужно детальнее изложить задачу, чтобы о них говорить.

 
Vladimir:

Это не двумерный массив, а одномерный массив с элементами - структурами. Коль скоро номер параметра уникален, то элементов столько же, сколько разных номеров. А не миллиард.

1. Этот массив можно вести, вставляя новые элементы в нужное место, а не просто добавлять элементы в конец. Тогда он будет упорядочен по номеру параметра, и будет работать двоичный поиск, очень быстрый.

Но тогда этот массив нужно заранее объявить и зарезервировать под него память. 


С бинарным поиском понятно. Но он применим к совсем простым массивам, а вдобавок ко всему нужно сортировать массив.


У меня в реальности задача намного сложнее. 

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

На самом деле, думал что это задача как-то хитро решена в программирование и есть простое не затратное по ресурсам решение

 
Sergey Likho:

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

На самом деле, думал что это задача как-то хитро решена в программирование и есть простое не затратное по ресурсам решение

Если то значение, по которому происходит поиск, уникальное, то все уже давно придумано - контейнер std::map в C++. Уникальное значение - ключ, по которому и происходит поиск. Под MQL4/5 вполне можно разработать аналог.

12
Новый комментарий
Причина обращения: