Эффективный алгоритм поиска значения в столбце

@SrgKord · Регистрация: 14.02.2013

Студворк — интернет-сервис помощи студентам

У меня происходит просмотр столбца А, и последовательный поиск каждого значения из этого столбца в столбце Б.
Эта процедура (одна строка кода) самая долгая. Обработка 500 строк с проверкой с таблице из 17000 строк (она фильтруется после запуска макроса по нужным критериям, но остаётся всё равно очень много строк) длится около 20 минут. А всё из-за последовательного повторения одной и той же операции с разными значениями.
Может есть более эффективные алгоритмы?

toiai · 14.07.2018, 21:44

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

@snipe · 14.07.2018, 22:21

а что в итоге-то должно получиться?
по мимо словаря
есть сводные таблицы
есть рекордсет

ну или на худой конец попытаться разогнать ваш код
(вот только где он)

@SrgKord · 15.07.2018, 04:18 **[ТС]**

toiai, snipe, я не выложил код, потому что он у вас просто не заработает, а тестовый образец не делал. Я проверил в пошаговом выполнении, какая строка кода съедает практически всё время. Из цикла выбросил всё, что там не обязательно.

Сейчас приложил. Книга1 - тот документ, где проводится проверка заявок. История списаний - база списанных заявок. Цель: найти дубли в текущем файле списания.

@SrgKord · 15.07.2018, 04:20 **[ТС]**

toiai, если вы скачали вариант без кнопки на ленте, то лучше скачайте новый вариант, добавил на ленту вызов процедуры

@Burk · 15.07.2018, 05:34

SrgKord, я так понял, что вы ищете 500 значений среди 17000 (архив не могу открыть у себя). Надо упорядочить лист Б по возрастанию и и искать не простым перебором, а методом половинного деления номеров строк с данными. Раз в 100 будет быстрее.

@snipe · 15.07.2018, 05:45

SrgKord, вы сами писали этот код или это чужое произведение
тут вот какое дело
любое обращение к листу
буть то Cells Range или вот у вас find
переключение между листами или как у вас между книгами
это потеря времени причем очень значительная
более того у вас запускается Книга1 а потом выключается
ну это пока первые впечатления

я так и не услышал что должно получиться по результатам работы кода

@SrgKord · 15.07.2018, 06:17 **[ТС]**

Сообщение от snipe

я так и не услышал что должно получиться по результатам работы кода

Результат - справа от таблицы появляются записи "Полный дубль", "Частичный дубль", "Запись уникальна"

Сообщение от snipe

вы сами писали этот код или это чужое произведение

Полностью сам

Сообщение от snipe

переключение между листами или как у вас между книгами

Там же стоит условие выбора

Visual Basic

1	If wb.Name Like "История списаний" Then

Visual Basic

1	If ws.Name Like "Все регионы" Then

Переключения никакого происходить не должно, под условия подходят только одна книга и один лист.

snipe, опишите подробнее, что вы наблюдали? Я ничего похожего не замечал.
В книге "История списаний" стоит один только макрос на Worksheet_change - его задача год писать в ячейку соответствующего поля автоматом.

Сообщение от Burk

Надо упорядочить лист Б по возрастанию и и искать не простым перебором, а методом половинного деления номеров строк с данными. Раз в 100 будет быстрее.

Благодарю, попробую реализовать!

Добавлено через 1 минуту

Сообщение от Burk

архив не могу открыть у себя

Может быть так? Пароль 1234

@SrgKord · 15.07.2018, 06:20 **[ТС]**

Не пойму, почему не добавляет архив

@Burk · 15.07.2018, 06:40

SrgKord, нарисовал макрос, первая строка листа - заголовки, предполагается, что ваши значения в ячейках строковые. Отсортируйте столбец Б по возрастанию

Visual Basic

Sub OneHalf()
Dim I As Long, Jb As Long, Jk As Long, LastA As Long, LastB As Long
Dim Sa As String, TF As Boolean
LastA = Cells(Rows.Count, 1).End(xlUp).Row
LastB = Cells(Rows.Count, 2).End(xlUp).Row
  For I = 2 To LastA
    Sa = Cells(I, 1): Jb = 2: Jk = LastB
    Do While Jk - Jb > 1
      J = Int((Jb + Jk) / 2): If J < 2 Then J = 2
      If Sa < Cells(J, 2) Then Jk = J Else Jb = J
    Loop
    J = IIf(Sa = Cells(Jb, 2), Jb, IIf(Sa = Cells(Jk, 2), Jk, 0))
    'если J = 0, то знаение не найдено
  Next
End Sub

@Alex77755 · 15.07.2018, 20:32

SrgKord, не верь этому!

Visual Basic

1	Sa = Cells(I, 1)

Visual Basic

1	If Sa < Cells(J, 2)

не дождёшься выполнения.
Массивы+словарь помогут ускорить значительно

@Burk · 16.07.2018, 05:05

Alex77755,

Сообщение от Alex77755

не дождёшься выполнения.

прежде чем делать такие заявления нужно создать модельный пример и проверить. У меня подобная схема работала на сравнении двух таблиц по 7000 строк каждый.
для 17000 строк будет всего 40 срвнений

@SrgKord · 16.07.2018, 07:21 **[ТС]**

Burk, благодарю! Разберусь, как устроен ваш пример, применю к своей задаче.

@Burk · 16.07.2018, 07:46

SrgKord, это сделано по первому вашему сообщению - столбец А что ищем, Б где. Если у вас там числа, то Sa описать как Long.

@Alex77755 · 16.07.2018, 15:21

Burk, даже если просто заменить Ваше

Visual Basic

1	Sa = Cells(I, 1)

На

Visual Basic

1	Sa =m(I, 1)

предварительно считав в массив, скорость увеличится на порядок.
Но у ТС немного другое требование: надо разделить на 3 группы: есть совпадение полное (Номер заявки+Партномер), есть частичное совпадение ( только Номер заявки) либо нет ни одного.
В этом случае необходимо создать словарь по большому файлу ("история списаний") за 1 проход по массиву с добавлением ключей Номер заявки+Партномер и Номер заявки
Потом идти по массиву Книга1 с проверкой вхождения в словарь Номер заявки+Партномер и Номер заявки
Если нет совпадений - уникальное
......дальше понятно?

@Burk · 16.07.2018, 17:17

Alex77755, ещё раз прочитайте моё предыдущее сообщение, я делал для исходного заказа автора, что там дальше не смотрел, если что-то изменилось, то надо создавать новую тему. Там правда у меня есть небольшая неточность - не сорок сравнений, а четырнадцать. Да и мне не хотелось бы с вами ломать копья по поводу не моей задачи, пишите не мне, а автору темы. Могу только добавить, что в моей бывшей задаче (про 7000 строк) время вычисления при подобной методике сократилось с 4 часов до 6 минут, правда задача была посложнее этой.

Добавлено через 35 минут

Сообщение от Alex77755

скорость увеличится на порядок.

Если вы имеете ввиду двоичный порядок, то да, в два раза быстрее

@SrgKord · 17.07.2018, 03:54 **[ТС]**

Сообщение от Alex77755

В этом случае необходимо создать словарь по большому файлу ("история списаний") за 1 проход по массиву с добавлением ключей Номер заявки+Партномер и Номер заявки
Потом идти по массиву Книга1 с проверкой вхождения в словарь Номер заявки+Партномер и Номер заявки

Т.е. вы бы создали два массива для Книга 1 и История списаний, или три массива: два для История списаний (партномер; партномер + заявка) и один для книги?

@Alex77755 · 17.07.2018, 08:19

Я бы считал одной строкой историю в массив. Потом загрузил в словарь с ключами Номер заявки+Партномер и Номер заявки
Потом считал в другой массив Книгу1
Потом шел бы по этому массиву с проверкой нахождения в словаре ключей
Есть ключ Номер заявки+Партномер значит полное совпадение
Есть ключ Номер заявки = частичное совпадение
В противном случае значение уникально
Результаты записывать в тот же массив
по окончании работы массив вывалить на лист
В итоге один проход по массиву историй и один по книге
А не 17472 х 541 считываний с листа и поиска на листе, которое тоже не быстрое

@Alex77755 · 17.07.2018, 08:55

Глубоко не вникал, но важное, вроде оставил
Макрос работал больше часа
Сейчас не больше 2с

@SrgKord · 20.07.2018, 09:42 **[ТС]**

Alex77755, Проникновенно прочитал ваш код, понравилось. Классно вы эти массивы со словарями веррррртите

Только зачем вы сделали второй словарь:

Visual Basic

1 2	Dim sl: Set sl = CreateObject("Scripting.Dictionary") Dim slp: Set slp = CreateObject("Scripting.Dictionary")

если он нигде не применяется?

Добавлено через 17 часов 43 минуты
Запустил сегодня вашу процедуру - супер, молниеносная обработка. Я теперь некоторые свои первые работы переделаю.

@SrgKord 49 / 31 / 2 Регистрация: 14.02.2013 Сообщений: 677
		1
	Эффективный алгоритм поиска значения в столбце 14.07.2018, 21:36. Показов 1993. Ответов 21 Метки алгоритм поиска (Все метки) У меня происходит просмотр столбца А, и последовательный поиск каждого значения из этого столбца в столбце Б. Эта процедура (одна строка кода) самая долгая. Обработка 500 строк с проверкой с таблице из 17000 строк (она фильтруется после запуска макроса по нужным критериям, но остаётся всё равно очень много строк) длится около 20 минут. А всё из-за последовательного повторения одной и той же операции с разными значениями. Может есть более эффективные алгоритмы? 0

toiai 3217 / 966 / 223 Регистрация: 29.05.2010 Сообщений: 2,085
	14.07.2018, 21:44	2
	Пример данных приложи и результат полученных данных тоже, тогда быстрей будет ответ. Предположу, что решение возможно со словарем... 0

@snipe 4039 / 1424 / 394 Регистрация: 07.08.2013 Сообщений: 3,546
	14.07.2018, 22:21	3
	а что в итоге-то должно получиться? по мимо словаря есть сводные таблицы есть рекордсет ну или на худой конец попытаться разогнать ваш код (вот только где он) 0

@SrgKord 49 / 31 / 2 Регистрация: 14.02.2013 Сообщений: 677
	15.07.2018, 04:20 [ТС]	5
	toiai, если вы скачали вариант без кнопки на ленте, то лучше скачайте новый вариант, добавил на ленту вызов процедуры 0

@Burk 1836 / 1152 / 353 Регистрация: 11.07.2014 Сообщений: 4,072
	15.07.2018, 05:34	6
	SrgKord, я так понял, что вы ищете 500 значений среди 17000 (архив не могу открыть у себя). Надо упорядочить лист Б по возрастанию и и искать не простым перебором, а методом половинного деления номеров строк с данными. Раз в 100 будет быстрее. 0

@snipe 4039 / 1424 / 394 Регистрация: 07.08.2013 Сообщений: 3,546
	15.07.2018, 05:45	7
	SrgKord, вы сами писали этот код или это чужое произведение тут вот какое дело любое обращение к листу буть то Cells Range или вот у вас find переключение между листами или как у вас между книгами это потеря времени причем очень значительная более того у вас запускается Книга1 а потом выключается ну это пока первые впечатления я так и не услышал что должно получиться по результатам работы кода 0

@Burk 1836 / 1152 / 353 Регистрация: 11.07.2014 Сообщений: 4,072
	16.07.2018, 05:05	12
	Alex77755, Сообщение от Alex77755 не дождёшься выполнения. прежде чем делать такие заявления нужно создать модельный пример и проверить. У меня подобная схема работала на сравнении двух таблиц по 7000 строк каждый. для 17000 строк будет всего 40 срвнений 0

@SrgKord 49 / 31 / 2 Регистрация: 14.02.2013 Сообщений: 677
	16.07.2018, 07:21 [ТС]	13
	Burk, благодарю! Разберусь, как устроен ваш пример, применю к своей задаче. 0

@Burk 1836 / 1152 / 353 Регистрация: 11.07.2014 Сообщений: 4,072
	16.07.2018, 07:46	14
	SrgKord, это сделано по первому вашему сообщению - столбец А что ищем, Б где. Если у вас там числа, то Sa описать как Long. 1

@Burk 1836 / 1152 / 353 Регистрация: 11.07.2014 Сообщений: 4,072
	16.07.2018, 17:17	16
	Alex77755, ещё раз прочитайте моё предыдущее сообщение, я делал для исходного заказа автора, что там дальше не смотрел, если что-то изменилось, то надо создавать новую тему. Там правда у меня есть небольшая неточность - не сорок сравнений, а четырнадцать. Да и мне не хотелось бы с вами ломать копья по поводу не моей задачи, пишите не мне, а автору темы. Могу только добавить, что в моей бывшей задаче (про 7000 строк) время вычисления при подобной методике сократилось с 4 часов до 6 минут, правда задача была посложнее этой. Добавлено через 35 минут Сообщение от Alex77755 скорость увеличится на порядок. Если вы имеете ввиду двоичный порядок, то да, в два раза быстрее 0

@SrgKord 49 / 31 / 2 Регистрация: 14.02.2013 Сообщений: 677
	17.07.2018, 03:54 [ТС]	17
	Сообщение от Alex77755 В этом случае необходимо создать словарь по большому файлу ("история списаний") за 1 проход по массиву с добавлением ключей Номер заявки+Партномер и Номер заявки Потом идти по массиву Книга1 с проверкой вхождения в словарь Номер заявки+Партномер и Номер заявки Т.е. вы бы создали два массива для Книга 1 и История списаний, или три массива: два для История списаний (партномер; партномер + заявка) и один для книги? 0

@Alex77755 11487 / 3774 / 678 Регистрация: 13.02.2009 Сообщений: 11,153
	17.07.2018, 08:19	18
	Я бы считал одной строкой историю в массив. Потом загрузил в словарь с ключами Номер заявки+Партномер и Номер заявки Потом считал в другой массив Книгу1 Потом шел бы по этому массиву с проверкой нахождения в словаре ключей Есть ключ Номер заявки+Партномер значит полное совпадение Есть ключ Номер заявки = частичное совпадение В противном случае значение уникально Результаты записывать в тот же массив по окончании работы массив вывалить на лист В итоге один проход по массиву историй и один по книге А не 17472 х 541 считываний с листа и поиска на листе, которое тоже не быстрое 0

Эффективный алгоритм поиска значения в столбце

Решение