Странные характеристики для заданных операций

Question

Все эти результаты были получены с помощью CPython 3.5.2.

Я заметил странные характеристики некоторых операций класса set.

Я измерил время, необходимое для выполнения объединения двух наборов, содержащих только целые числа. Конечно, это время зависит от размеров наборов. Удивительно, но это также зависит от «плотности» целых чисел. Здесь представлен график:

Ось й является суммой размеров двух наборов (которые были выбраны случайным образом и независимо друг от друга, для каждого опыта). Ось y - это время, в секундах (в шкале журнала).

Плотность d означает, что наборы были созданы путем выборки N целых чисел из общего числа N/d целых чисел. Другими словами, для плотности 0,5 возьмем одну половину целых чисел некоторого интервала, тогда как для плотности 0,1 возьмем одну десятую целых чисел некоторого (большего) интервала.

Это минимальный код для получения некоторых результатов (при необходимости я могу опубликовать полный код, который я использовал для сюжета, но он длиннее).

import time 
import random 
import numpy 

def get_values(size, density): 
    return set(random.sample(range(int(size/density)), size)) 

def perform_op(size, density): 
    values1 = get_values(size, density) 
    values2 = get_values(size, density) 
    t = time.time() 
    result = values1 | values2 
    return time.time()-t 

size = 10000000 
for density in [0.05, 0.1, 0.5, 0.99]: 
    times = [perform_op(size, density) for _ in range(10)] 
    print('density: %.2f, mean time: %.4f, standard deviation: %.4f' % (density, numpy.mean(times), numpy.std(times))) 

Союз:

density: 0.05, time: 0.9846, standard deviation: 0.0440 
density: 0.10, time: 1.0141, standard deviation: 0.0204 
density: 0.50, time: 0.5477, standard deviation: 0.0059 
density: 0.99, time: 0.3440, standard deviation: 0.0020 

Существует примерно коэффициент 3 для вычисления времени между самым быстрым и самым медленным, с множества, имеющие одинаковый размер . Кроме того, для низких плотностей существует гораздо большая изменчивость.

Забавная вещь состоит в том, для пересечения (заменить values1 | values2 на values1 & values2 в perform_op функции), мы также не постоянное представление, но модель отличается:

density: 0.05, time: 0.3928, standard deviation: 0.0046 
density: 0.10, time: 0.4876, standard deviation: 0.0041 
density: 0.50, time: 0.5975, standard deviation: 0.0127 
density: 0.99, time: 0.3806, standard deviation: 0.0015 

Я не проверял другие установленные операции ,

Я не понимаю, почему существуют такие различия. Из того, что я знаю, наборы Python реализованы с помощью хеш-таблиц, поэтому плотность целых чисел не должна иметь значения, пока их хэши хорошо распределены.

Каково происхождение этих разных выступлений?

Answer 1

Есть два основных фактора, способствующими здесь:

1. Вы продуцирующие различные выходы размера; с плотными входами, подавляющее большинство значений будет перекрываться, поэтому вы получите гораздо меньшие результаты.
2. int имеет очень простой хеш-код; это просто значение int. Итак, hash(1234) == 1234. С плотными входами это означает, что вы имеете в основном смежные хеш-коды без перекрытия, потому что значения всегда меньше, чем количество кодов set (например, с 100 000 значений, у вас есть 262 144 ковши, когда значения плотны, ваши хэш-коды диапазон от 0 до 101,010, так что фактическое обтекание не происходит по модулю 262,144).Более того, хэш-коды, в основном последовательные, означают, что доступ к памяти осуществляется в основном последовательным шаблоном (помогая эвристике выборки кэша ЦП). Для редких входов это не применяется; у вас будет много не равных значений хэш в одном и том же ведре (поскольку каждое из 2 000 000 значений для случая 0.05 имеет 7-8 разных значений, которые будут хешировать в том же ковше, когда имеется 262 144 ковши). Поскольку Python использует закрытое хеширование (так называемую открытую адресацию), столкновение с неравными значениями приводит к переполнению всей памяти (что не позволяет кешу центрального процессора помочь), чтобы найти ведро для нового значения.

Чтобы продемонстрировать проблему Ковша столкновения:

>>> import random 
>>> vals = random.sample(xrange(int(100000/0.99)), 100000) 
>>> vals_sparse = random.sample(xrange(int(100000/0.05)), 100000) 

# Check the number of unique buckets hashed to for dense and sparse values 
>>> len({hash(v) % 262144 for v in vals}) 
100000 # No bucket overlap at all 
>>> len({hash(v) % 262144 for v in vals_sparse}) 
85002 # ~15% of all values generated produced a bucket collision 

Каждые из этих значений, попадающих должно прыгать вокруг set ищет незанятое ведро, плотные значения не сталкиваются на всех, так они полностью избегают этой стоимости.

Если вы хотите тест, который фиксирует обе проблемы (в то же время, используя плотные и разреженные входы), попробуйте его float с (которые не эквивалентны int значений, поскольку float хеширования пытается хэширования в int эквивалентную float к то же значение, что и int). Чтобы избежать разрозненных уровней фактически равных значений, выберите входы от неперекрывающихся значений, поэтому разреженный и плотный не изменяет размер полученного объединения. Это код, я использовал, который заканчивается с достаточно однородным разом, независимо от плотности:

import time 
import random 
import numpy 

def get_values(size, density, evens=True): 
    if evens: 
     # Divide by 100. to get floats with much more varied hashes 
     vals = random.sample([x/100. for x in xrange(0, int(size/density * 2), 2)], size) 
    else: 
     vals = random.sample([x/100. for x in xrange(1, int(size/density * 2), 2)], size) 
    return set(vals) 

def perform_op(size, density): 
    values1 = get_values(size, density) 
    values2 = get_values(size, density, False) # Select from non-overlapping values 
    t = time.time() 
    result = values1 | values2 
    return time.time()-t, len(result) 

size = 100000 
for density in [0.05, 0.1, 0.5, 0.99]: 
    times = [perform_op(size, density) for _ in range(10)] 
    resultlens = [r for _, r in times] 
    times = [t for t, _ in times] 
    print('density: %.2f, mean time: %.4f, standard deviation: %.4f' % (density, numpy.mean(times), numpy.std(times))) 
    print(numpy.mean(resultlens))