Pull to refresh

Comments 31

Поправьте, быстрая сортировка имеет не логарифмическую сложность, а O(n log n)
Если уж говорить стого, то O(n^2), если будем рассматривать произвольные данные.
В худшем случае — да, но есть много ухищрений, чтобы его избежать.
UFO landed and left these words here
Ну это надо быть полным неудачником, чтобы попасть на worst case (например, все элементы массива одинаковы).
Average case для быстрой сортировки O(n log n) и ориентируются всегда на него.
Не забывайте, что вероятность получения worst case для массива уже из 100 чисел составляет менее 10^-200 при более-менее нормальной реализации алгоритма. Поэтому для быстрой сортировки используется оценка средней сложности, которая как раз составляет O(n log n).
А если индусы разработчики реализовали добавление нового числа в отсортированный массив, и прогоняют еще раз сортировку?
Если вы предполагаете наличие индусов в коде, вам может помочь перемешивание массива перед его сортировкой.
Даааа, а еще есть вероятность получить O(n). Причем на случайных данных, она почти такая же.
А что в экселевском VBS со встроенной сортировкой?
Наверняка же она там есть, и есть шанс, что быстрее написанного на VB любого алгоритма, не искали?
И что насчет сортировки не через VBS, а «стандартной» операцией над диапазоном ячеек?
Дальнейшую обработку уже можно и в VB.
Максимум вылить на лист данные и использовать сортировку, которая доступна через пользовательский интерфейс.
Встроенная сортировка Excel работает намного быстрее чем сортировка через VBA.
Время доступа к ячейке разное.

Включаем запись макроса
Выделяем вручную столбец
Сортируем кнопкой
Заканчиваем запись макроса

На выходе получаем код VBA который вызывает стандартную, встроенную сортировку.
Правильно ли я понял, что так можно отсортировать данные непосредственно на листе? К сожалению, мне нельзя изменять порядок данных.
Макросом копируем данные во временную таблицу, сортируем как надо и обрабатываем. Макросом через родные функции это будет быстрее, чем через VBA.

Сделайте код через макросы и откорректируйте как надо.
А если использовать хэш-таблицы, то сложность вообще будет линейной в среднем.
Вот это:
For i = 0 To DistinctCount - 1
    IsUnique = False
    If DistinctValues(i) = Values(row, col) Then
        //При наличии совпадения, мы закрашиваем соответствующую ячейку на листе красным.
        IsUnique = True
        ....

должно наверное быть записано так:
IsUnique = True
For i = 0 To DistinctCount - 1
    If DistinctValues(i) = Values(row, col) Then
        //При наличии совпадения, мы закрашиваем соответствующую ячейку на листе красным.
        IsUnique = False
        ....

Да, конечно. У меня был небольшой диссонанс между именем переменной и тем, что она показывает, почему-то значение false соответствовало уникальности, и наоборот.
Еще она выставлялась в False на каждой итерации цикла, а проверялась после его окончания.
О, да. Было когда-то нечто похожее. К счастью мне ничего «подкрашивать» не было нужно, только небольшая дополнительная аналитика. Я сделал скрипт excel -> sqlite. А дальше — старый добрый SQL. Я вам сочувствую.
Первое, что пришло в голову после постановки задачи — использование ассоциативных контейнеров (хеш то бишь), так что не разделяю некоторого пафоса подачи.

А в общем случае, давно уже привык к «народной истине» о том, что у программистов не бывает задач, меньше чем на час. То есть не надо спешить и обязательно реализовывать самый простой алгоритм или самый частный случай; если делаешь хоть что-то, что может пригодиться еще раз, то стоит оставить некоторый задел для масштабируемости или расширяемости (это несомненно включает и понятие алгоритмической сложности). У всех проектов, конечно этот критерий допустимой сложности решения различный, но если что-то можно сделать за 5 минут «плохо», а за час «хорошо» — всегда стоит выбирать второй вариант.
Никакого пафоса, что вы. Я ни в коем случае не пытаюсь показать, что мое решение самое лучшее, или что-то в этом роде.

если что-то можно сделать за 5 минут «плохо», а за час «хорошо» — всегда стоит выбирать второй вариант.


Полностью разделяю ваше мнение. Однако стоит учитывать, насколько трата времени на улучшение решения в том или ином смысле (будь то временная или пространственная сложность, масштабируемость, переносимость или что-то еще) окупится для каждого конкретного случая. Иногда можно легко перестараться, и начать строить экскаватор для того, чтобы выкопать яму для посадки дерева во дворе.

К сожалению в данном случае я был ограничен не только по времени, но и по выбору средства решения задачи, и выбранное мной соотношение «время/качество результата» привело меня к такому решению, которое я представил.
Для того чтобы подкрасить совпадающие идентификаторы в экселе, наверное стоило бы в первую очередь отсортировать набор и настроить т.н. «условное форматирование».

Но, безусловно, это было бы куда менее творческое решение
Возможно я неверно истолковал условие задачи, но если в 2010 Excel выделяю область ячеек, скажем 5 на 5. И нажимаю кнопочку "условное форматирование", там есть "повторяющиеся значения". Все подкрасилось розовым без какой-либо модификации данных. (без сортировки)
На сколько я понял идею автора, первое попадание за повторение не считается. Красным выделять второе и последующие попадения идентификатора.

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


И да. можно без сортировки:

Но не знаю как поведет себя на объемах.

А, если с сортировкой, то формула проще — достаточно сравнить с предыдущим значением и за объемы не страшно
Ой, кажись я совершенно не правильно понял суть требуемого.

Vampiro, предложенное вами решение, судя по всему, помимо того что более простое, еще и подходящее.
Так наверное будет более близко к исходному скрипту автора
image
Да что ж такое… В третий раз и на те же грабли… Здесь просто поиск дубликатов, без ухищерений. Стандартное условное форматирование полностью подходит :facepalm
Похоже, Ваше «простое решение» не будет находить совпадающие элементы, если они находятся в одном столбце.
TL;DR А в чем проблема-то? Почему массив именно двумерный, если задача от его двумерности никак не зависит?

Поиск повторений — это задача поиска (well, duh!). Она хорошо проанализирована. Предполагаем, что элементы массива берутся из линейно упорядоченного множества. Проходим по массиву, собирая находу дерево поиска: для каждого элемента проверяем, есть ли он в дереве (O(log n)); если есть, то заносим его в список дубликатов (O(1)), если нет, то заносим его в дерево (O(log n)).

Итого — O(n(1 + log n + log n)) = O(n log n). Зачем было разводить туеву хучу текста?
Only those users with full accounts are able to leave comments. Log in, please.