Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 31
Поправьте, быстрая сортировка имеет не логарифмическую сложность, а O(n log n)
Спасибо, исправил.
Если уж говорить стого, то O(n^2), если будем рассматривать произвольные данные.
В худшем случае — да, но есть много ухищрений, чтобы его избежать.
Ну это надо быть полным неудачником, чтобы попасть на worst case (например, все элементы массива одинаковы).
Average case для быстрой сортировки O(n log n) и ориентируются всегда на него.
Average case для быстрой сортировки O(n log n) и ориентируются всегда на него.
Не забывайте, что вероятность получения worst case для массива уже из 100 чисел составляет менее 10^-200 при более-менее нормальной реализации алгоритма. Поэтому для быстрой сортировки используется оценка средней сложности, которая как раз составляет O(n log n).
Даааа, а еще есть вероятность получить O(n). Причем на случайных данных, она почти такая же.
А что в экселевском VBS со встроенной сортировкой?
Наверняка же она там есть, и есть шанс, что быстрее написанного на VB любого алгоритма, не искали?
И что насчет сортировки не через VBS, а «стандартной» операцией над диапазоном ячеек?
Дальнейшую обработку уже можно и в VB.
Наверняка же она там есть, и есть шанс, что быстрее написанного на 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
....
О, да. Было когда-то нечто похожее. К счастью мне ничего «подкрашивать» не было нужно, только небольшая дополнительная аналитика. Я сделал скрипт excel -> sqlite. А дальше — старый добрый SQL. Я вам сочувствую.
Первое, что пришло в голову после постановки задачи — использование ассоциативных контейнеров (хеш то бишь), так что не разделяю некоторого пафоса подачи.
А в общем случае, давно уже привык к «народной истине» о том, что у программистов не бывает задач, меньше чем на час. То есть не надо спешить и обязательно реализовывать самый простой алгоритм или самый частный случай; если делаешь хоть что-то, что может пригодиться еще раз, то стоит оставить некоторый задел для масштабируемости или расширяемости (это несомненно включает и понятие алгоритмической сложности). У всех проектов, конечно этот критерий допустимой сложности решения различный, но если что-то можно сделать за 5 минут «плохо», а за час «хорошо» — всегда стоит выбирать второй вариант.
А в общем случае, давно уже привык к «народной истине» о том, что у программистов не бывает задач, меньше чем на час. То есть не надо спешить и обязательно реализовывать самый простой алгоритм или самый частный случай; если делаешь хоть что-то, что может пригодиться еще раз, то стоит оставить некоторый задел для масштабируемости или расширяемости (это несомненно включает и понятие алгоритмической сложности). У всех проектов, конечно этот критерий допустимой сложности решения различный, но если что-то можно сделать за 5 минут «плохо», а за час «хорошо» — всегда стоит выбирать второй вариант.
Никакого пафоса, что вы. Я ни в коем случае не пытаюсь показать, что мое решение самое лучшее, или что-то в этом роде.
Полностью разделяю ваше мнение. Однако стоит учитывать, насколько трата времени на улучшение решения в том или ином смысле (будь то временная или пространственная сложность, масштабируемость, переносимость или что-то еще) окупится для каждого конкретного случая. Иногда можно легко перестараться, и начать строить экскаватор для того, чтобы выкопать яму для посадки дерева во дворе.
К сожалению в данном случае я был ограничен не только по времени, но и по выбору средства решения задачи, и выбранное мной соотношение «время/качество результата» привело меня к такому решению, которое я представил.
если что-то можно сделать за 5 минут «плохо», а за час «хорошо» — всегда стоит выбирать второй вариант.
Полностью разделяю ваше мнение. Однако стоит учитывать, насколько трата времени на улучшение решения в том или ином смысле (будь то временная или пространственная сложность, масштабируемость, переносимость или что-то еще) окупится для каждого конкретного случая. Иногда можно легко перестараться, и начать строить экскаватор для того, чтобы выкопать яму для посадки дерева во дворе.
К сожалению в данном случае я был ограничен не только по времени, но и по выбору средства решения задачи, и выбранное мной соотношение «время/качество результата» привело меня к такому решению, которое я представил.
Для того чтобы подкрасить совпадающие идентификаторы в экселе, наверное стоило бы в первую очередь отсортировать набор и настроить т.н. «условное форматирование».
Но, безусловно, это было бы куда менее творческое решение
Но, безусловно, это было бы куда менее творческое решение
Возможно я неверно истолковал условие задачи, но если в 2010 Excel выделяю область ячеек, скажем 5 на 5. И нажимаю кнопочку "условное форматирование", там есть "повторяющиеся значения". Все подкрасилось розовым без какой-либо модификации данных. (без сортировки)
На сколько я понял идею автора, первое попадание за повторение не считается. Красным выделять второе и последующие попадения идентификатора.
И да. можно без сортировки:
Но не знаю как поведет себя на объемах.
А, если с сортировкой, то формула проще — достаточно сравнить с предыдущим значением и за объемы не страшно
берем каждую ячейку таблицы, и сравниваем ее со всеми ячейками, которые находятся после нее (стоит отметить, что в том столбце, где вхождение элемента встречается первый раз, повторений быть не может, поэтому мы начинаем сравнение со следующего столбца), и, если находим совпадения, красим их красным цветом.
И да. можно без сортировки:
Но не знаю как поведет себя на объемах.
А, если с сортировкой, то формула проще — достаточно сравнить с предыдущим значением и за объемы не страшно
Похоже, Ваше «простое решение» не будет находить совпадающие элементы, если они находятся в одном столбце.
TL;DR А в чем проблема-то? Почему массив именно двумерный, если задача от его двумерности никак не зависит?
Поиск повторений — это задача поиска (well, duh!). Она хорошо проанализирована. Предполагаем, что элементы массива берутся из линейно упорядоченного множества. Проходим по массиву, собирая находу дерево поиска: для каждого элемента проверяем, есть ли он в дереве (O(log n)); если есть, то заносим его в список дубликатов (O(1)), если нет, то заносим его в дерево (O(log n)).
Итого — O(n(1 + log n + log n)) = O(n log n). Зачем было разводить туеву хучу текста?
Поиск повторений — это задача поиска (well, duh!). Она хорошо проанализирована. Предполагаем, что элементы массива берутся из линейно упорядоченного множества. Проходим по массиву, собирая находу дерево поиска: для каждого элемента проверяем, есть ли он в дереве (O(log n)); если есть, то заносим его в список дубликатов (O(1)), если нет, то заносим его в дерево (O(log n)).
Итого — O(n(1 + log n + log n)) = O(n log n). Зачем было разводить туеву хучу текста?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск повторений в двумерном массиве, или вычислительная сложность на примере