Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: Пред. 1 2 3 4 5 6 7 8 След.
RSS
Сортировка в двумерном массиве VBA Excel, Написал тут небольшую процедурку, может кому будет полезна
 
#31
21.12.2017 00:35:02
Там тонуть то особо негде :) У меня на рабочем файле есть ряд макросов, которые переплюнут по размеру все в тестовом файле, и ничего ведь не выкинешь...

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

Да, там есть еще найденная на просторах интернета функция по расчету занимаемой в данный момент экселем оперативной памяти.
Jack Famous, именно на нее и ругался 64-х битный эксель. Т.е. можно ее вырезать без ущерба для всего остального.

Вот тест на 60000 элементов (массив 60к*10):
Скрытый текст

П.С: О внутреннем таймере по оценке производительности внутреннего сортировщика ключей я тоже задумывался) Добавить его не трудно. Также бедет добавлен микс по типам данных для проверки работы последнего макроса.
П.П.С: Чуть не забыл - там еще несколько функций разного толка, они вроде все прокомментированы в начале.
Изменено: oldy7 - 21.12.2017 01:24:05
 
 
 
#32
21.12.2017 09:43:27
Подкину дровишек в топку творчества...
Мой любимый принцип сортировки, а также я его использую для добычи уникальных значений.
Порезал все что можно чтоб сделать визуализацию самого принципа.
Вкратце массив представляется пилой, где зубья - фрагменты, определенные как отсортированные участки. С каждой проходкой их становится в два раза меньше. Последний нечетный ждет когда станет четным. Вот, наверно, и все описание, остальные комментарии в коде.
Оригинальный код значительно больше и быстрее, но могу скинуть позже, если интересно... (просто его надо привести в нормальный вид :) )
Впрочем, если есть интерес, можем в рамках данной темы сделать это поэтапно, чтоб читателям была понятна вся логика конечного продукта, а то специально для себя переписывать лень...
Изменено: AAF - 21.12.2017 10:00:15
 
 
 
#33
21.12.2017 10:47:42
Цитата
AAF написал:
если есть интерес
интерес определённо есть))))
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
 
 
#34
21.12.2017 12:23:49
AAF, интерес конечно есть) Вроде такой метод "расчёской" в википедии называют.

Пытаюсь вспомнить основы и с помощью OR и XOR операторов вычислить правильную позицию куска текста в итоговом массиве. Получается какая-то ерунда. Корень квадратный из суммы квадратов числовых значений символов тоже)
Изменено: oldy7 - 21.12.2017 13:09:03
 
 
 
#35
21.12.2017 12:27:19
Этому коду в новогодние каникулы будет 20 лет, а Вики тогда еще не было, вроде...  :D
Цитата
oldy7 написал:
вычислить правильную позицию куска текста в итоговом массиве.
А зачем?
Изменено: AAF - 21.12.2017 12:32:12
 
 
 
#36
21.12.2017 13:17:45
Цитата
AAF написал:
Этому коду в новогодние каникулы будет 20 лет, а Вики тогда еще не было, вроде...  
Всегда приятно быть первооткрывателем)

Цитата
AAF написал:
А зачем?
Такие методы, как "пузырёк" и ряд других слепо сравнивают только соседние элементы. Когда есть представление (математически высчитанная позиция) куда элемент должен попасть без промежуточных перестановок, то так вроде быстрее) Во всяком случае в отношении числовых данных  буду копать в этом направлении. Например есть массив чисел от 1 до 10, все числа перемешаны между собой в произвольном порядке. По значению элемента без всяких промежуточных перестановок понятно, где этот элемент должен находится в итоге.
---------
По строкам. Есть встроенная (не знаю с какой версии VBA) функция StrComp(sting1,string2,compare) - сравнивает строковые значения между собой: больше или меньше. Видимо при простом сравнении if string1>string2 then автоматом вызывается эта функция интерпретатором. Остается выяснить каким образом эта функция определяет какая строка меньше и наоборот. Со строками одинаковой длины все понятно.
Любовался на итоги сортировки строк и заметил, что если все первые несколько символов одинаковые, то сравнение идет по следующему (если он есть). Осталось раскидать все полкам, придумать какие вводные данные запихать в словарь для дальнейшей обработки сортировщиком, и собственно как реализовать сам алгоритм без лишних перестановок в массиве.
Изменено: oldy7 - 21.12.2017 13:41:28
 
 
 
#37
22.12.2017 02:42:50
Добавил грубую сортировку к "раку" и производительность увеличилась вдвое.
 
 
 
#38
23.12.2017 13:14:13
Прикрутил к своему коду с индексацией через словарь сортировщики Слэна (QuickSort) и AAF. И там и там влетел в бесконечный цикл...
AAF, нет желания глянуть что не так касательно Вашего кода? Может я чего намудрил... Но поменял только массивы и пару переменных.
----------
Тем временем "пузырь" также обзавелся ускорителем в виде однопроходной массированной переброски элементов с одной половины массива в другую. Смысл заложен следующий:
- берется исходный массив
- в его рамках сравниваются элементы в нижней половине массива с верхней. Большие улетают вверх, меньшие вниз.
- похожая операция между четвертями: 1/4-2/4, 2/4-3/4, 3/4-4/4
- и снова шаг один только нижняя половина просматривается в другом направлении. Как правило перед этим этапом остается менее 5% тормозов - элементов занимающих не свою половину массива. Т.е. подметаем остатки.
- далее управление переходит основному сортировщику.

Для мин-макса такой вариант не подойдет, а жаль.
Изменено: oldy7 - 23.12.2017 13:21:06
 
 
 
#39
23.12.2017 19:30:51
Код
Win7x64, MSO2013x32, Intel Core i3-4130/4GB
Нерегулируемы параметры: По возрастанию, Compare Bin, Empty = 0
Массив 300000x1 (длина строки = 32)
Sort_6                                            2,410
Sort_Excel (Compare Text!)                        0,824

Код
Sub ApplySamle() 'пример сортировки по нескольким столбцам
Dim a 'входящий массив
Dim a0() as long 'входящий массив с индексами
Dim aC 'массив с номерами сортируемых столбцов
Dim aResult 'результирующий массив
Dim c 'сортируемый столбец
Dim i As Long, j As Long
Dim t1 As Single, t2 As Single
a = Range("A1:J100000").Value 'загрузка Вашего массива
t1 = Timer
ReDim a0(LBound(a) To UBound(a))
For i = LBound(a) To UBound(a)
  a0(i) = i
Next
aC = Array(5, 2, 4, 8, 1, 3, 6, 7, 9, 10)
For Each c In aC
  Sort_6 a, c, a0
Next
ReDim aResult(LBound(a0) To UBound(a0), LBound(a, 2) To UBound(a, 2))
For j = LBound(a, 2) To UBound(a, 2)
  For i = LBound(a0) To UBound(a0)
    aResult(i, j) = a(a0(i), j)
  Next
Next
t2 = Timer
MsgBox t2 - t1
a = Empty: a0 = Empty
End Sub


Цитата
oldy7 написал:
AAF, нет желания глянуть
Неа  :D
Возьмите код из файлика, там все в порядке.
Изменено: AAF - 31.12.2017 03:19:06
 
 
 
#40
23.12.2017 20:21:29
AAF, спасибо :) Очень хорошие результаты. Близки к экселевскому. Пока запустить не удалось на Excel 2007, но верю на слово)
-----
Маленький тест:
Скрытый текст
Чтож... Несмотря на ностальгическую привязанность к несчастному пузырьку с ним придется попрощаться. Никакие костыли не исправят его медлительность.

Постараюсь к концу завтрашнего дня допилить "аналитика" :)
Изменено: oldy7 - 23.12.2017 21:43:48
 
 
 
#41
23.12.2017 20:42:14
Осталось только нарисовать функцию-менеджер, которая в зависимости от требуемых параметров раскидывала задачи по специализированным процедурам, тогда еще не много можно времени скроить... Требуемые параметры тоже можно обсудить и тогда рисовать. Одному лень...
Изменено: AAF - 23.12.2017 20:43:42
 
 
 
#42
23.12.2017 21:48:15
Цитата
oldy7 написал:
Пока запустить не удалось на Excel 2007
Что не так? Я файлик исправил, там ссылка на процедуру из другого файла была, может поэтому?
Изменено: AAF - 23.12.2017 21:53:06
 
 
 
#43
23.12.2017 21:57:32
Функцию или процедуру. Например:
- нужна сортировка: да/нет
- если да, то столбец/столбцы, направление, как реагировать на различные типы данных, промежуточный массив или брать с листа
- группировка похожих записей по столбцу: да/нет
- исключение типов данных: да/нет (например на вход 1 - числа, 2 - даты, 3 - текст)
- консолидация отличных (от слова "отличие") данных в строке по столбцу с объединением в строке-образце - но это я бы поручил отдельной процедуре, так быстрее
- удаление дубликатов строк (тоже лучше в отдельную процедуру)

Плюс в связке с универсальным сортировщиком группу функций для массивов, по аналогии с формулами в Excel: VlookUp; CountIf; SummIf  и пр.. Причем можно налепить функций с одни параметром или массивом. Простор для творчества)
Изменено: oldy7 - 23.12.2017 21:58:30
 
 
 
#44
23.12.2017 23:56:47
Цитата
AAF написал:
Что не так? Я файлик исправил, там ссылка на процедуру из другого файла была, может поэтому?
Да, вначале. Потом я по аналогии со своим демо пытался привязать к верхней кнопке разные макросы, предполагая что они запускают шоу) В общем разобрался.

На моем драндулете вот такой результат.
 
 
 
#45
24.12.2017 01:00:17
Цитата
oldy7 написал:
На моем драндулете вот такой результат
А массив по всем столбцам, как в примере 100000x10?
Я еще внес исправления (Sort_4) в сообщение 39.
Изменено: AAF - 24.12.2017 01:01:29
 
 
 
#46
24.12.2017 02:26:08
AAF, пять столбцов с шагом 1. Ваш сортер же по одному столбцу сортирует вроде.
Перепроверил. Да, результаты всегда одни и те-же. На разных машинах сортировщики работают по разному - это нормально. Тот-же двупроходный пузырь на рабочем компе выдал результаты вдвое лучшие, чем на домашнем. Наверняка еще от замусоренности системы зависит, свою уже года полтора не переставлял.
Скрытый текст
Изменено: oldy7 - 24.12.2017 02:53:48
 
 
 
#47
24.12.2017 06:23:20
Цитата
oldy7 написал:
Ваш сортер же по одному столбцу сортирует вроде
Сортировки по нескольким столбцам не бывает, потому-как она является продуктом последовательной сортировки по нескольким столбцам, где последняя является основной, а все предыдущие получаются вложенными в последующую в обратном порядке.
Цитата
AAF написал:
ApplySamle() 'пример сортировки по нескольким столбцам
в сообщении 39 - тому пример.
 
 
 
#48
24.12.2017 11:11:27
Цитата
AAF написал:
Сортировки по нескольким столбцам не бывает, потому-как она является продуктом последовательной сортировки по нескольким столбцам, где последняя является основной, а все предыдущие получаются вложенными в последующую в обратном порядке.
Значит пора сказку сделать былью :) Хотя не получится, что печально. Даже если делать в рамках одной процедуры с фиксированным количеством сортируемых столбцов, то один черт придется каждый раз ворошить весь двумерный массив. Или массив индексов по нему.
----
Нарыл в сети вариант сортировки через библиотеки системы. Но там похоже только по возрастанию. Автор Aртём Скробов он же tyomitch. Пока не тестировал.
 
 
 
#49
26.12.2017 20:00:29
Написал предварительный вариант сортировщика для чисел (пока). Есть варианты улучшения.

Алгоритм сортировки и реализация:
- на старте входящий массив (опорный столбец) разбивается на группы по типу данных, их будет три: числа во всех вариациях, даты (решил им выделить отдельный сегмент и второй приоритет при дальнейшей выгрузке отсортированного массива), текст.
- на этапе индексации в т.ч. определяются минимальные и максимальные значения для чисел и дат
- непосредственно перед сортировкой вычисляется некий коэффициент по формуле: kf = (max - min) / ubound (arr)
- цикл по массиву уникальных числовых значений
- берем число, и в зависимости от значения коэффициента делим на него или умножаем (<1 - умножаем, >1 - делим)
- таким образом мы получаем примерную позицию в массиве, где это число должно находится
- проверяем свободно ли место во втором массиве (переливка данных из одного в другой)
- если свободно то помещаем элемент-число туда
- если занято, то ищем пустое место рядом
- далее определяем какое из чисел больше/меньше с дальнейшим смещением/заменой мест

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

Вот картинка с тестом:
Скрытый текст
 
 
 
#50
27.12.2017 05:22:18
Цитата
oldy7 написал:
если занято, то ищем пустое место рядом
Например есть массив. Индексы тоже имеются. Какой будет результирующий массив? Индексы просьба от значений не отрывать.
Код
idx 1 2 3 4 5 6 7 8 9 
val 1 3 4 4 4 5 7 4 9
Результат при первой проходке:
idx ?
val ?
 
 
 
#51
27.12.2017 18:33:23
Цитата
AAF написал:
Например есть массив. Индексы тоже имеются. Какой будет результирующий массив?
У меня сортируются уникальные значения, т.е. результат: 1,3,4,5,7,9. Один общий цикл по элементам, далее по ситуации. Либо сразу на место - если пусто в приёмном массиве. Либо текущий (взятый из первичного массива) элемент протаскивается до нужного места, или до пустой ячейки.
- берем элемент, делим/умножаем на коэффициент
- если пусто , то заселяем
- проверяем не является ли определенная поисковиком пустот позиция основанием, или вершиной массива. Если да, то соотв.Do...Loop пока не встанет на свое место, либо не наткнется на пустоту. Заселяем
- примерно тоже самое с пустотами снизу/сверху от полученной координаты.
- если попали в окружение других элементов, то сравниваем больше/меньше в обе стороны. Протаскиваем элемент до нужного места по выбранному результатом сравнения направлению до нужного места - если вниз, то пока не упремся в элемент меньший, если вверх, то наоборот.

Проходка за один цикл. Для ускорения нет своппинга - сравнили, если нужно смещать дальше, то запись объекта сравнения на текущую позицию. Сравнения всегда либо Х-1, либо Х+1. Похожий способ записи был использован в предыдущем сортере.
Цитата
AAF написал:
Индексы просьба от значений не отрывать.
Индексами занимается словарь в самом начале. При сортировке они не задействованы. Загнали опорный столбец в словарь, заиндексировали, отсортировали, перелили по индексам в новый массив.

П.С.: Но словарь - это долго, буду менять систему индексации.
Скрытый текст
Изменено: oldy7 - 27.12.2017 18:42:00
 
 
 
#52
28.12.2017 06:08:05
Первоначальный вариант:
Скрытый текст
После небольшой оптимизации поиска пустот:
Скрытый текст
 
 
 
#53
28.12.2017 12:09:29
Лет 5-ь назад искал сортировщик - тогда перебрал кучу вариантов. "Пузырек" отпал сразу.
нашел для себя интересный вариант. Тут такого вроде пока не было:

Код
Sub aQSort2(ByRef a() As Variant, ByVal N As Integer, ByRef low As Long, ByRef high As Long)
Dim i As Long, j As Long, k As Long
Dim m As Variant, wsp As Variant
i = low
j = high
m = a(Round((i + j) \ 2), N)
Do Until i > j
    Do While a(i, N) < m
        i = i + 1
    Loop
    Do While a(j, N) > m
        j = j - 1
    Loop
    If (i <= j) Then
        For k = LBound(a, 2) To UBound(a, 2)
        wsp = a(i, k)
        a(i, k) = a(j, k)
        a(j, k) = wsp
        Next k
        i = i + 1
        j = j - 1
    End If
Loop
If (low < j) Then aQSort2 a(), N, low, j
If (i < high) Then aQSort2 a(), N, i, high
End Sub

Где нашел уже не упомню докинул его в файлы от oldy7 и AAF. В приложении.

Судя по всему, (если я все верно  вставил)  - работает хорошо :) .:

Скрытый текст


PS\
Перевложил один файл в архив  по указанию модератора.
Изменено: SLAVICK - 03.01.2018 18:23:03
 
 
 
#54
28.12.2017 14:12:12
SLAVICK, спасибо за подарок.
Сделал версию с сортировкой индексов, чтоб можно было без перезаписи основного массива сортировку по нескольким столбцам делать, а также сортировку выборки получить... Sort_6 тоже подкрутил. :)
Вот, получились такие результаты:
Код
300000x1 (длина строки = 32)
QSort2_Test              0,988
Sort_6                   0,883
QSort2Idx_Test           0,871
Sort_Excel  Compare Text 0,793
Изменено: AAF - 28.12.2017 14:22:47
 
 
 
#55
28.12.2017 14:46:00
AAF - это к новому году :).

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

Все равно встроенную сортировку, к сожалению пока  не нашел как обогнать.
 
 
 
#56
28.12.2017 14:48:04
Цитата
SLAVICK написал:
встроенную сортировку, к сожалению пока  не нашел как обогнать
Сомневаюсь, что это реально...
И Вас с Новым годом!!! :)
 
 
 
#57
28.12.2017 18:58:00
SLAVICK, Спасибо) QuickSort тоже не помешает.
AAF, прекрасные результаты! Особенно на тексте... Идеал уже близок.
-------
Есть стимул к оптимизации моего кода)
Замерял давеча на рабочем компе время затраченное на индексацию через словарь. Результаты удручающие. И это был набросок на более быстрый , чем у меня стоит на сортерах сейчас, алгоритм индексации. Видимо придется двигать при сортинге еще и индексы... С другой стороны при хорошем КПД сортера эти дубликаты уже не помеха) Допилю тестер по индексации и выложу сюда.

По поводу текста посматриваю на всяческие троичные деревья) Т.е. результат не скоро.
----------
Очередная модернизация сортера :) Вместо много условного досортера приведённого ранее использовал "рака".
Скрытый текст
Кому интересно - пример самого простого сортировщика. Проще пузыря и значительно его быстрее.
Скрытый текст
Изменено: oldy7 - 30.12.2017 10:03:31
 
 
 
#58
28.12.2017 21:55:43
SLAVICK, в aQSort2 с множественной сортировкой, к сожалению, будут проблемы, т. к. для повторяющихся значений в сортируемом массиве не соблюдается порядок индексов согласно их изначального положения. Т. е. желаемого результата вложенности сортировки может и не быть...  :(
Но для простого получения уникальных значений или для сортировки одномерного массива пойдет.
Изменено: AAF - 29.12.2017 11:56:23
 
 
 
#59
29.12.2017 01:19:31
SLAVICK, приведите размер файлов в соответствие с правилами (суммарно не более 100 кБ)
 
 
 
#60
29.12.2017 05:38:48
AAF, там ошибка в макросе... В общем результаты удалил, потом перетестирую.
---------
Ещё немного подкрутил:
Скрытый текст
Изменено: oldy7 - 29.12.2017 20:59:01
 
 
 
Страницы: Пред. 1 2 3 4 5 6 7 8 След.
Наверх