В общем представьте цикл на 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 итераций :) Таким образом это можно воспринимать как "времянку", если мало ресурсов и прочее.
Есть такой старый добрый "Метод половинного деления", гуглица спокойно, если я правильно интерпретировал ваш калеканский.
П.С. вообще, если честно, чёткого представления того что вы пытались делать и что хотите получить - нету.
Что известно про заполненные ячейки? Они образуют непрерывный фрагмент? Прижат ли он к началу массива, или к концу, или у него известна минимальная длина?
Если ваш алгоритм применить к массиву, в котором заполнены ячейки с 10001 по 19999, он их не заметит, и скажет, что массив пуст. Так и предполагается?
Если заполнен непрерывный участок с неизвестной заранее длиной L, то есть простой способ найти его за O(N/L) операций (а потом обработать за O(L)).
Если он непрерывный можно свести трудоемкость к O(n/2) пустив два итератора с конца и начала.
А вот если он кусочный то тут уже веселее.
В любом случае нужен ответ автора вопроса)
Николай Павлов: O(n/2) слишком долго, к тому же, оно равно O(n). Можно найти быстрее :)
А если кусочный - это то же самое, что произвольный. Нужен прямой перебор. Хотя есть ещё ситуации заранее заданного числа кусков, или известного числа ненулевых элементов.
Одномерный морской бой получается :)
Mrrl: долго, но железно. Честно говоря сложно придумать однопоточный алгоритм для такой задачи, чтобы он быстрее O(n) работал. А вот с многопоточным окружением можно попробовать просто разделить отрезок на сегменты.
Николай Павлов: Возьмите ту же "расчёску" - просмотр массива со всё уменьшающимся шагом. Она найдёт непрерывный фрагмент, как только шаг станет меньше либо равен длине этого фрагмента. При правильной организации хватит 2*N/L просмотров (в худшем случае).
Что-то я совсем не понял.
Первая итерация мы смотрим Array[10000] и если он не !=0 то что делаем дальше? идем назад или вперед? откуда у вас данные что 0 не в первом или последующем промежутке?
У нас будет 10 итераций с шагом 10.000, если на одном из шагов ячейка массива заполнена, значит пора прочёсывать его. Но чтобы наверняка знать что мы заденем все его заполненные ячейки, мы вернемся на шаг.
Urukhayy: И установим новый шаг в единицу. Как индикатор. Мы летим с бешеной скоростью тупо пропуская группы ячеек, но заметив заполненную мы понимаем, что "долетели" до заполненных, и возвращаемся на шаг назад, дабы слизать все заполненные более тщательно. (шагом в единицу)
Николай Павлов: Хотел узнать что лучше, какой вариант. Вдруг понадобится цикл в миллион итераций, причем 90% из всех итераций будут пустыми по каким-то причинам?
Насколько я понял, вы пытаетесь реализовать что-то вроде классической дихотомии. Но мне кажется что в вашем случае это не сработает, т.к. вы не знаете, где именно находятся нули, и вам при любом раскладе придётся обойти тупо все ячейки и для каждой выполнить действие. Так что не парьтесь и фигачьте циклом.
Нет информации о том, что за массив, откуда он взялся. Чтобы применять подобный алгоритм, нужно знать о закономерностях расположения информации в массиве. Вы такой информации не предоставили, поэтому сказать, эффективен ли ваш алгоритм, не представляется возможным. Если размещение данных в массиве случайное, то полный перебор решит проблему.
Как вариант, можно попробовать отсортировать массив по значению, определить положение первого ненулевого элемента и начинать работать с него. Ну или сортировать по убыванию и обходить массив до встречи первого нулевого элемента. Но производительность подобного решения надо предварительно тестировать, раз уж она вас волнует.
Интерпретирую поток сознания автора вопроса:
Дано - ?
Решение - такое-то.
Вопрос - подходит ли данное решение?
Ответ, равноценный вопросу - "а зачем вы спгашиваете?"
Но любопытство победило лень )
Насколько я понял, автору нужно обработать непустые элементы массива. Большого массива.
Вариант 1
Вспомнить аббревиатуру KISS: перебирать все элементы по порядку и не изобретать велосипедов, в которых потом по два дня будете баги искать. А так же свести к минимуму риск быть проклятым тем человеком, которому ваш код достанется по наследству. if (Array[i] == 0) continue; не такая уж и дорогая инструкция.
Вариант 2
Если массив приходит сортированный - проходить его с заполненного края.
Если нет - сортировать нет смысла. На сортировку потратите в любом случае больше времени чем на один проход по массиву.
Вариант 3
Если можете влиять на заполнение массива значениями, не вставляйте пустых, а только те, которые надо обработать.
В общем, для нормальной оптимизации в любом случае нужно больше входных данных.
