Всем здрасте. Интересует наиболее быстрый алгоритм вычисления числа вхождения элементов одного массива в другой. Конкретно в моем случае, массивы - это натуральные числа, для упрощения скажем от1 до 20 В примере у меня есть решение через встроенные функции, и через VBA. Есть ли более быстрые алгоритмы?
зы. Функция у меня для примера алгоритма, в действительности это будет макрос и работа не с ячейками, а с массивами. Надо провести несколько миллионов сравнений.
Всем здрасте. Интересует наиболее быстрый алгоритм вычисления числа вхождения элементов одного массива в другой. Конкретно в моем случае, массивы - это натуральные числа, для упрощения скажем от1 до 20 В примере у меня есть решение через встроенные функции, и через VBA. Есть ли более быстрые алгоритмы?
зы. Функция у меня для примера алгоритма, в действительности это будет макрос и работа не с ячейками, а с массивами. Надо провести несколько миллионов сравнений.Michael_S
Michael_S, если возможна сортировка 2ого массив то я бы: отсортировал и потом при сравнении с первым доходил не до конца 2 ого массив, а делал проверку А может ли там быть этот элемент?
20 4 5 5 19 14 15 12 18 20 14 5 10 19
первый проход до конца второй выбывает третий 1 раз и т д
думаю быстрей будет
Michael_S, если возможна сортировка 2ого массив то я бы: отсортировал и потом при сравнении с первым доходил не до конца 2 ого массив, а делал проверку А может ли там быть этот элемент?
20 4 5 5 19 14 15 12 18 20 14 5 10 19
первый проход до конца второй выбывает третий 1 раз и т д
Матраскин, в принципе оба массива отсортированы по возрастанию... вот только по проходам я не пронял... в моем вариант всего 8=6=14 циклов, какой алгоритм вы предлагаете?
Матраскин, в принципе оба массива отсортированы по возрастанию... вот только по проходам я не пронял... в моем вариант всего 8=6=14 циклов, какой алгоритм вы предлагаете?Michael_S
Michael_S, берём элемент №1 массива№1 сравниваем с элементом №1 массива №2. Если этот элемент < элемента №1 массива№2, то сравниваем с элементом №2 массива№2. Если больше то конец цикла, элемента элемент №1 массива№1 нет в массиве №2. Если равен - то элемент найден, счётчик увеличивается на +1 и выходим из цикла. И так повторяем пока не закончиться массив №1
p.s. массив №2 отсорт. по возрастанию
Michael_S, берём элемент №1 массива№1 сравниваем с элементом №1 массива №2. Если этот элемент < элемента №1 массива№2, то сравниваем с элементом №2 массива№2. Если больше то конец цикла, элемента элемент №1 массива№1 нет в массиве №2. Если равен - то элемент найден, счётчик увеличивается на +1 и выходим из цикла. И так повторяем пока не закончиться массив №1
Если массив отсортирован, можно применить метод половинного деления. Берем средний элемент во втором массиве и сравниваем с элементом с первого массива. Если элементы равны, счетчик увеличиваем и переходим к поиску следующего элемента с первого массива, иначе определяем в какой части второго массива может быть элемент с первого массива и снова делим его пополам и т.д. до тех пор пока или элементы будут равны или размер части второго массива станет = 1.
Если массив отсортирован, можно применить метод половинного деления. Берем средний элемент во втором массиве и сравниваем с элементом с первого массива. Если элементы равны, счетчик увеличиваем и переходим к поиску следующего элемента с первого массива, иначе определяем в какой части второго массива может быть элемент с первого массива и снова делим его пополам и т.д. до тех пор пока или элементы будут равны или размер части второго массива станет = 1. SergeyKorotun
Варианты, предложанные на Планете не смотрел, предложу свои Если данных очень много, лучше работать на массивах
Вариант 1, принцип такой же как и у тебя, создаем массив флагов, и пробегаем по одному массиву и по другому Достоинства: небольшое количество итераций, сложность O(n+m), не требует сортировки данных Недостатки: может потребоватся большое количество памяти, в зависимости от значений в массивах, работает только с целыми числами
Вариант 2, в основе принцип предложенный Матраскиным, оба массива отсортированы по возрастанию, пробегаем по первому массиву, сравниваеваем с элементами второго, до тех пор, пока элемент второго массива не будет равен первому, или превышать, пока не закончатся данные, при этом следущий элемент первого массива сравнивается не с начала второго массива, а с запомненного смещения, тем самым обеспечивается меньшее кол-во итерций, не превышающее n+m Достоинства: небольшое количество итераций, сложность O(n+m) в худшем случае, не требует выделение памяти, может работать с целыми и дробными числами, а также со строковыми переменными, отсортированными по возрастанию Недостатки: данные должны быть отсортированы по возрастанию
Т.к. сложность алгоритмов линейна в обоих вариантах, и количество итераций не превышает n+m, то сравнение двух массивов по миллиону элементов составляет доли секунды, второй варинт получился быстрее (в зависимости от данных)
Варианты, предложанные на Планете не смотрел, предложу свои Если данных очень много, лучше работать на массивах
Вариант 1, принцип такой же как и у тебя, создаем массив флагов, и пробегаем по одному массиву и по другому Достоинства: небольшое количество итераций, сложность O(n+m), не требует сортировки данных Недостатки: может потребоватся большое количество памяти, в зависимости от значений в массивах, работает только с целыми числами
Вариант 2, в основе принцип предложенный Матраскиным, оба массива отсортированы по возрастанию, пробегаем по первому массиву, сравниваеваем с элементами второго, до тех пор, пока элемент второго массива не будет равен первому, или превышать, пока не закончатся данные, при этом следущий элемент первого массива сравнивается не с начала второго массива, а с запомненного смещения, тем самым обеспечивается меньшее кол-во итерций, не превышающее n+m Достоинства: небольшое количество итераций, сложность O(n+m) в худшем случае, не требует выделение памяти, может работать с целыми и дробными числами, а также со строковыми переменными, отсортированными по возрастанию Недостатки: данные должны быть отсортированы по возрастанию
Т.к. сложность алгоритмов линейна в обоих вариантах, и количество итераций не превышает n+m, то сравнение двух массивов по миллиону элементов составляет доли секунды, второй варинт получился быстрее (в зависимости от данных)MCH
[quote=MCH]Что Вам мешает сделать счетчик и вывести в окно Immediate?[/quote] только собираюсь начинать изучать VBA [quote=MCH]Сделал счетчик[/quote] не вижу
[quote=MCH]Что Вам мешает сделать счетчик и вывести в окно Immediate?[/quote] только собираюсь начинать изучать VBA [quote=MCH]Сделал счетчик[/quote] не вижуSergeyKorotun
Снова всем здравствуйте! Появилось немного времени и желания вновь вернуться к этой теме. Прежде всего спасибо всем ответившим. Есть интересные предложения для общего случая небольших массивов данных, но ... из преложенных наиболее подходящим будет "Вариант 2", предложенный MCH.
Есть лотерея - 5 из 36, проходит ежедневно. Есть архив тиражей, (на сегодняшний день - 1340). Существует ошибочное мнение, что на анализе статистики можно "угадать Джек-пот - от 400 000 руб, (на сегодня - это более 17 млн) Знаю, затея бесполезная и бессмысленная, но "...сердце верит в чудеса" (С) Потому, что идея бессмысленная, и возвращаюсь к ней от нечего делать, когда есть время. В листе "Все варианты" будет около 400 000 строк и столбцов по количеству тиражей - т.е. всего около 600 млн. заполненных ячеек ЮДФ здесь явно не подходит.
В файле пример с частичной реализацией. После разрешения макросов произойдет загрузка тиражей за 2013 год. Если после загрузки нажать кнопку "Обновить все", а потом еще раз запустить макрос - будет таблица всех тиражей.
Снова всем здравствуйте! Появилось немного времени и желания вновь вернуться к этой теме. Прежде всего спасибо всем ответившим. Есть интересные предложения для общего случая небольших массивов данных, но ... из преложенных наиболее подходящим будет "Вариант 2", предложенный MCH.
Есть лотерея - 5 из 36, проходит ежедневно. Есть архив тиражей, (на сегодняшний день - 1340). Существует ошибочное мнение, что на анализе статистики можно "угадать Джек-пот - от 400 000 руб, (на сегодня - это более 17 млн) Знаю, затея бесполезная и бессмысленная, но "...сердце верит в чудеса" (С) Потому, что идея бессмысленная, и возвращаюсь к ней от нечего делать, когда есть время. В листе "Все варианты" будет около 400 000 строк и столбцов по количеству тиражей - т.е. всего около 600 млн. заполненных ячеек ЮДФ здесь явно не подходит.
В файле пример с частичной реализацией. После разрешения макросов произойдет загрузка тиражей за 2013 год. Если после загрузки нажать кнопку "Обновить все", а потом еще раз запустить макрос - будет таблица всех тиражей.Michael_S
Миш, а озвучь какую задачу хочешь решить, с точки зрения комбинаторики возможно интересно будет порешать. 500 млн чисел (376992 * 1340) для массивов - плевое дело перебрать.
Не ради лотереи, а ради комбинаторики могу помочь.
Миш, а озвучь какую задачу хочешь решить, с точки зрения комбинаторики возможно интересно будет порешать. 500 млн чисел (376992 * 1340) для массивов - плевое дело перебрать.
Не ради лотереи, а ради комбинаторики могу помочь.MCH
Миш, да задача пока, на первом этапе, простая. Для лисов Пары-Четверки показать, когда и сколько выпадала эта комбинация; для "Все" показать кол-во совпадений каждого варианта в каждом тираже. Есть у меня (в мозгах) еще один алгоритм, там кол-во переборов в два раза меньше, но не уверен, что в общем случае это будет быстрее.
Да и, честно говоря - скорость обработки здесь не решающий фактор. Пусть даже, при первом расчете будет обрабатывать сутки (хотя думаю, что даже на не самом оптимальном алгоритме займет не более часа), потом только добавлять вновь появившиеся данные. Была бы от этого хоть какая-то (материальная) польза - уже б сделал. А так - только моральное удовлетворение, ...и немалые материальные потери, если на эти расчеты положиться. А если и повезет - то не благодаря расчетам
Миш, да задача пока, на первом этапе, простая. Для лисов Пары-Четверки показать, когда и сколько выпадала эта комбинация; для "Все" показать кол-во совпадений каждого варианта в каждом тираже. Есть у меня (в мозгах) еще один алгоритм, там кол-во переборов в два раза меньше, но не уверен, что в общем случае это будет быстрее.
Да и, честно говоря - скорость обработки здесь не решающий фактор. Пусть даже, при первом расчете будет обрабатывать сутки (хотя думаю, что даже на не самом оптимальном алгоритме займет не более часа), потом только добавлять вновь появившиеся данные. Была бы от этого хоть какая-то (материальная) польза - уже б сделал. А так - только моральное удовлетворение, ...и немалые материальные потери, если на эти расчеты положиться. А если и повезет - то не благодаря расчетам Michael_S
Сообщение отредактировал Michael_S - Воскресенье, 04.08.2013, 17:48
Да и, честно говоря - скорость обработки здесь не решающий фактор.
Думаю что для задач двойки, тройки, четверки - перебор займет секунды
Твой файл не смотрел, но могу предложить следующий алгоритм Для пар: генерируем выборку 2 из 36, проверяем все 630 (36*35/2) вариантов на 1340 тиражей, сортируем по убыванию и выводим на экран, с указанием номеров тиражей, где совпадало Для троек аналогично, только времени затратится больше: 7140 вариантов (36*35*34/6), для четверок - 58905 вариантов Но учитывая, что количество вариантов не такое уж и большое, то времени затратится немного
Да и, честно говоря - скорость обработки здесь не решающий фактор.
Думаю что для задач двойки, тройки, четверки - перебор займет секунды
Твой файл не смотрел, но могу предложить следующий алгоритм Для пар: генерируем выборку 2 из 36, проверяем все 630 (36*35/2) вариантов на 1340 тиражей, сортируем по убыванию и выводим на экран, с указанием номеров тиражей, где совпадало Для троек аналогично, только времени затратится больше: 7140 вариантов (36*35*34/6), для четверок - 58905 вариантов Но учитывая, что количество вариантов не такое уж и большое, то времени затратится немногоMCH
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
