Постоянно встречается задача проверки наличия значения в массиве. В PHP для этих целей часто используют функцию in_array которая принимает два аргумента: искомое значение (или массив значений) и массив, в котором будет произведён поиск. Если значение найдено, функция возвращает true, в противном случае false.
Описание проблемы
Пока значений в массиве немного, то всё работает быстро. Но как только массив разрастается до 10 000 – 20 000 элементов, начинаются проблемы.
Один мой скрипт должен был проверять элементы на уникальность, сделать это средствами БД не получалось, т.к. массив после запроса к базе модифицировался пару раз. В массиве хранились только числовые id элементов (это пригодится для решения). В какой-то момент элементов стало больше 60 000 и скрипт стал работать по 20-30 с. на локальном хосте, что крайне медленно.
Простым замером времени исполнения участков кода (с помощью функции microtime()) что проблема именно в in_array.
Решение проблемы
Если подумать, то перебирать весь массив каждый раз чтобы проверить существование в нём элемента глупо. Гораздо проще проверить существование конкретного элемента массива, без перебора остальных значений. Для этого вместо массива вида ключ => значение(ID элемента) нужно использовать массив вида ключ(ID элемента) => какое-то значение (например true).
В таком случае для проверки существования элемента в массиве достаточно использовать функцию isset(), в которую следует передавать переменную вида $имя_массива[искомый ID элемента].
После перехода на такой способ проверки скрипт стал отрабатывать за 1.2 с, что вполне нормально.
Искренне Ваш К.О. =)
10 комментариев
А пример можете написать, потому что так не очень ясно.
Ответить
Основная идея проста: поменять местами ключ и значение в ассоциативном массиве. Т.е. в коде вместо:
будет
Где вместо true может быть что угодно. В итоге чтобы проверить есть ли этот элемент в массиве, достаточно проверить определён ли искомый ключ:
Ответить
Результат для python:
>>> timeit.timeit(‘import random\narr = {}\nfor i in range(60000):\n val=random
.random()\n arr[random.random()]=val\n if i == 30000:\n valu=val\nfor k,v i
n arr.iteritems():\n if v == val:\n print True’, number=100)
4.579244164521924
>>>
коротенько поясню:
импортируем модуль random
создаём словарь вида arr[]=
и ключ и значение — float
на 30000 шаге запоминаем значение (чтобы было потом по чему проверять наличие значения)
и соответственно теперь проверяем есть ли среди 60000 значений искомое. Если есть выводим True
Запихиваем всё это в timeit и прогоняем сто раз для верности.
Выше показано время для ста итераций. То есть в среднем одна итерация проходит за
0.045 секунды.
Это на создание массива и поиска нужного ключа по значению
Ответить
Ты не совсем понял суть написанного =) Я просто предлагаю проверять наличие ключа. А не перебирать каждый раз массив.
Но сейчас попробую повторить твой эксперимент.
Ответить
А можно написать простой однострочник
inArray = lambda arr, value: value in arr.itervalues()
Ответить
Выполняем вот это:
Получаем эпичные 18.884446144104 секунд *CRAZY*
Ответить
А если исправить ошибку и создавать только 60 000 элементов вместо 600 000, то получается нормуль — 2.09117436409. Вот только rand() возвращает целое. Я сейчас перепишу на float.
Ответить
С float получаем 2.4262247085571. Нормуль, я считаю.
Ответить
Окончательный вариант кода:
Ответить
Спасибо, ты гений)))
Ответить