Цикл в 100.000 итераций vs «умного» цикла?

Question

[Urukhayy]

В общем представьте цикл на 100.000 итераций. И условие такое, что производить нам действие надо с теми итерациями, при которых i = ячейке массива, значение которого не 0. Иначе говоря - if (Array[i] == 0) continue;
Так вот. Что будет быстрей, такой цикл в 100.000 итераций, или его аналог с алгоритмом?
Суть алгоритма такова: изначально шаг итерации равен не единице, а десяти тысячам: 0,10000,20000,30000,40000.. Затем ставим проверочку, не заполнена ли Array[i]. И, стало быть если она заполнена, значит мы "пролетели", но всего на 10.000 итераций. Далее шаг итераций ставим на единицу, и устанавливаем i-=10000.
Таким образом при аналогичной проверке первый цикл совершает 100.000 итераций, а второй столько, сколько требует заполненность массива + лишние 10.000 итераций.

P.S. метод полезен лишь в том случае, когда у вас заполнены не все 100.000 ячеек массива, а к примеру до 30%.

Хотя, если взять во внимание правило того, что зачем нужны вообще лишние ячейки или если у нас будут заполнены все 100.000 ячеек, нам все равно придется делать 100.000 итераций :) Таким образом это можно воспринимать как "времянку", если мало ресурсов и прочее.

Answer 1

[Дмитрий Энтелис]

Мне кажется что написан какой то бред если честно

Answer 2

[microphone]

Есть такой старый добрый "Метод половинного деления", гуглица спокойно, если я правильно интерпретировал ваш калеканский.
П.С. вообще, если честно, чёткого представления того что вы пытались делать и что хотите получить - нету.

Answer 3

[Mrrl]

Что известно про заполненные ячейки? Они образуют непрерывный фрагмент? Прижат ли он к началу массива, или к концу, или у него известна минимальная длина?
Если ваш алгоритм применить к массиву, в котором заполнены ячейки с 10001 по 19999, он их не заметит, и скажет, что массив пуст. Так и предполагается?
Если заполнен непрерывный участок с неизвестной заранее длиной L, то есть простой способ найти его за O(N/L) операций (а потом обработать за O(L)).

Comments

[Mrrl]

Николай Павлов: O(n/2) слишком долго, к тому же, оно равно O(n). Можно найти быстрее :)
А если кусочный - это то же самое, что произвольный. Нужен прямой перебор. Хотя есть ещё ситуации заранее заданного числа кусков, или известного числа ненулевых элементов.
Одномерный морской бой получается :)

[Mrrl]

Николай Павлов: Возьмите ту же "расчёску" - просмотр массива со всё уменьшающимся шагом. Она найдёт непрерывный фрагмент, как только шаг станет меньше либо равен длине этого фрагмента. При правильной организации хватит 2*N/L просмотров (в худшем случае).

Answer 4

[iliyaisd]

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

Answer 5

[Владлен Грачев]

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

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

Answer 6

[zhaparoff]

Интерпретирую поток сознания автора вопроса:
Дано - ?
Решение - такое-то.
Вопрос - подходит ли данное решение?
Ответ, равноценный вопросу - "а зачем вы спгашиваете?"

Но любопытство победило лень )
Насколько я понял, автору нужно обработать непустые элементы массива. Большого массива.

Вариант 1
Вспомнить аббревиатуру KISS: перебирать все элементы по порядку и не изобретать велосипедов, в которых потом по два дня будете баги искать. А так же свести к минимуму риск быть проклятым тем человеком, которому ваш код достанется по наследству.
if (Array[i] == 0) continue; не такая уж и дорогая инструкция.

Вариант 2
Если массив приходит сортированный - проходить его с заполненного края.
Если нет - сортировать нет смысла. На сортировку потратите в любом случае больше времени чем на один проход по массиву.

Вариант 3
Если можете влиять на заполнение массива значениями, не вставляйте пустых, а только те, которые надо обработать.

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

Answer 7

[Catrinblaidd]

100000 итераций, Вы серьёзно?

$arr = \range (0, 100000);
$res = [];
$start = \microtime(true);
$i = 0; 
for ($i; $i<100000; ++$i) {
  if ($arr[$i] != 0) {
    $res[$i] = $arr[$i];
  }
}
$end = \round(\microtime(true) - $start, 2);
echo $end;