Блог

Реальная проблема: у меня есть API, который возвращает не более 5000 элементов. В любой момент времени я могу видеть, сколько элементов существует, путем фильтрации по ценовому диапазону. Я также могу найти самый дорогой элемент.Мне нужно разбить эти элементы на ценовые диапазоны размером 5000 (размер узла), чтобы я мог собрать их все.

Практический пример ниже.

Заполнить список.

 price_list = []
for i in range(0, 100000):
    price_list.append(random.uniform(0, 100000))
 

Реализовать функцию поиска.

 def get_prange_count(startp, endp):
    return len([r for r in price_list if r <= endp and r >= startp])
 

Используя функцию get_prange_count, разбейте все элементы в price_list на узлы не более 5000.

например

 [{"startp": 0, "endp": 3.5, "item_count": 5000}, 
{"startp": 3.51, "endp": 4.03, "item_count": 5000}]

 

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

Заранее спасибо за любые рекомендации,

Редактировать:

 5000 -> 2 for demonstration purposes. 

price_list = [0.1, 0.2, 0.4, 1.3, 1.6, 5.0]

node1 = {"startp": 0, "endp": 0.2, "item_count": 2}
node2 = {"startp": 0.4, "endp": 1.3, "item_count": 2}
node3 = {"startp": 1.6, "endp": 5.0, "item_count": 2}
 

Это решение на Python использует только функции get_prange_count() и get_max_price() , как вы заявили, для поиска диапазонов цен по 5 тыс. элементов каждый. Ну, мне также нужна минимальная дельта-цена между двумя ценами, которые не совпадают — я предполагаю, что это единица, но 0,001 можно использовать для центов.

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

 import random

price_list_size = random.choice(range(90_000, 100_000))
price_list = random.choices(range(100_000), k=price_list_size)

delta_price = 1     # Minimum difference between any two different prices.

def get_prange_count(startp, endp):
    return len([r for r in price_list if startp <= r <= endp])

def get_max_price():
    return max(price_list)

def get_5k(mn=0, mx=get_max_price(), num=5_000):
    count = get_prange_count(mn, mx)
    delta_mx = (mx - mn) / 2
    while count != num and delta_mx >= delta_price / 2:
        mx  = -delta_mx if count > num else  delta_mx
        count, delta_mx = get_prange_count(mn, mx), delta_mx / 2
    return mx, count

def get_all_5k(mn=0, mx=get_max_price(), num=5_000):
    partmax, partcount = get_5k(mn, mx, num)
    result = [(mn, partmax, partcount)]
    while partmax < mx:
        partmin = partmax   delta_price
        partmax, partcount = get_5k(partmin, mx, num)
        result.append((partmin, partmax, partcount))
    return result

if __name__ == '__main__':
    print(f"Using {price_list_size} random prices from 0 to {get_max_price()}")
    result = get_all_5k()
    print(f"Splits into {len(result)} bins of approx 5000 elements")
    for mn, mx, count in result:
        print(f"  From {mn:8.1f} ... {mx:8.1f} with {count} items.")
 

Пример вывода:

 Using 96625 random prices from 0 to 99997
Splits into 20 bins of approx 5000 elements
  From      0.0 ...   5144.3 with 4998 items.
  From   5145.3 ...  10266.7 with 5001 items.
  From  10267.7 ...  15504.7 with 5000 items.
  From  15505.7 ...  20584.7 with 4999 items.
  From  20585.7 ...  25701.0 with 4997 items.
  From  25702.0 ...  30907.7 with 5000 items.
  From  30908.7 ...  36111.7 with 4999 items.
  From  36112.7 ...  41304.5 with 5000 items.
  From  41305.5 ...  46588.4 with 5000 items.
  From  46589.4 ...  51771.6 with 4999 items.
  From  51772.6 ...  56861.7 with 5000 items.
  From  56862.7 ...  62156.4 with 5001 items.
  From  62157.4 ...  67289.8 with 4999 items.
  From  67290.8 ...  72393.2 with 5000 items.
  From  72394.2 ...  77545.3 with 5000 items.
  From  77546.3 ...  82747.2 with 5003 items.
  From  82748.2 ...  87995.3 with 5000 items.
  From  87996.3 ...  93270.8 with 4999 items.
  From  93271.8 ...  98331.3 with 5001 items.
  From  98332.3 ... 101660.9 with 1599 items.
 

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

ОСТАНОВИТЬ НАЖАТИЕ!

Я перечитал ваш вопрос, и в нем написано не более 5 тыс. Если вы внесете в него следующее изменение get_5k , двоичный поиск будет таким же, как и раньше, но если он превышает 5 кб и delta_mx будет достаточно мал для выхода из внешнего цикла while, новый внутренний цикл while уменьшается mx до count <= 5 кб.

 def get_5k(mn=0, mx=get_max_price(), num=5_000):
    count = get_prange_count(mn, mx)
    delta_mx = (mx - mn) / 2
    while count != num and delta_mx >= delta_price / 2:
        mx  = -delta_mx if count > num else  delta_mx
        count, delta_mx = get_prange_count(mn, mx), delta_mx / 2
        # Assure count < num
        while count > num and delta_mx < delta_price / 2 and mx > mn:
            mx -= delta_price
            count = get_prange_count(mn, mx)
    return mx, count
 

Пример вывода:

 Using 95007 random prices from 0 to 99999
Splits into 19 bins of approx 5000 elements
  From      0.0 ...   5236.8 with 5000 items.
  From   5237.8 ...  10564.6 with 5000 items.
  From  10565.6 ...  15872.4 with 4998 items.
  From  15873.4 ...  21146.7 with 5000 items.
  From  21147.7 ...  26417.0 with 4999 items.
  From  26418.0 ...  31730.9 with 5000 items.
  From  31731.9 ...  36962.1 with 5000 items.
  From  36963.1 ...  42165.8 with 4998 items.
  From  42166.8 ...  47382.0 with 5000 items.
  From  47383.0 ...  52662.6 with 5000 items.
  From  52663.6 ...  57884.3 with 5000 items.
  From  57885.3 ...  63183.5 with 5000 items.
  From  63184.5 ...  68374.5 with 4999 items.
  From  68375.5 ...  73688.2 with 5000 items.
  From  73689.2 ...  78915.4 with 4998 items.
  From  78916.4 ...  84297.7 with 5000 items.
  From  84298.7 ...  89515.5 with 4999 items.
  From  89516.5 ...  94709.1 with 5000 items.
  From  94710.1 ... 105287.2 with 4991 items.
 

ОСТАНОВИТЬ НАЖАТИЕ # 2!!

Дальнейшее тестирование показывает, что предыдущий код удаляет элементы. Следующее не удаляет элементы и остается ниже 5k

 def get_5k(mn=0, mx=get_max_price(), num=5_000):
    "Mainly binary search for num items between mn and mx, adjusting mx"
    count = get_prange_count(mn, mx)
    delta_mx = (mx - mn) / 2
    while count != num and delta_mx >= delta_price / 2:
        mx  = -delta_mx if count > num else  delta_mx
        mx = mx // 1    # Floor
        count, delta_mx = get_prange_count(mn, mx), delta_mx / 2
        # Assure count < num
        # while count > num and delta_mx < delta_price / 2 and mx > mn:
        #     mx -= delta_price
        #     count = get_prange_count(mn, mx)
    return mx, count
 

Добавьте следующую проверку в конец:

 if __name__ == '__main__':
    if len(price_list) != sum(count for mn, mx, count in result):
        print("nWhoops! Some items missing:")
        p = price_list.copy()
        for mn, mx, count in result:
            items = _get_prange(mn, mx)
            assert len(items) == get_prange_count(mn, mx)
            for i in items:
                p.remove(i)
        p.sort()
        print(p)
 

Вывод теперь выглядит так:

 Using 100941 random prices from 0 to 99999
Splits into 21 bins of approx 5000 elements
  From      0.0 ...   4918.0 with 4998 items.
  From   4919.0 ...   9863.0 with 5000 items.
  From   9864.0 ...  14901.0 with 4998 items.
  From  14902.0 ...  19708.0 with 4999 items.
  From  19709.0 ...  24605.0 with 5000 items.
  From  24606.0 ...  29555.0 with 5000 items.
  From  29556.0 ...  34539.0 with 5000 items.
  From  34540.0 ...  39507.0 with 5000 items.
  From  39508.0 ...  44602.0 with 4997 items.
  From  44603.0 ...  49462.0 with 5000 items.
  From  49463.0 ...  54458.0 with 4999 items.
  From  54459.0 ...  59432.0 with 5000 items.
  From  59433.0 ...  64315.0 with 5000 items.
  From  64316.0 ...  69416.0 with 4998 items.
  From  69417.0 ...  74389.0 with 4998 items.
  From  74390.0 ...  79253.0 with 4999 items.
  From  79254.0 ...  84149.0 with 5000 items.
  From  84150.0 ...  89134.0 with 5000 items.
  From  89135.0 ...  94059.0 with 5000 items.
  From  94060.0 ...  99055.0 with 5000 items.
  From  99056.0 ... 100934.0 with 955 items.
 

Поскольку вы можете найти самый дорогой товар, выполните двоичный поиск по ценам от 0 до максимальной цены, чтобы найти самую высокую цену p , чтобы было меньше 5000 товаров с ценой от 0 до p , используя get_prange_count в качестве функции оценки в двоичном поиске. Поиск завершается, поскольку для поиска требуется только конечное число цен (с точностью до 2 цифр).

Например, если get_prange_count(0, max) = 6000 , вычислить c = get_prange_count(0, max/2) . Если c = 4000 , скажем, продолжить, get_prange_count(max/2, max) чтобы найти самую высокую цену p , такую, что get_prange_count(max/2, p) < 6000 - c = 2000 . Таким образом, размер блока меняется и является параметром рекурсивного двоичного поиска.

Затем вы можете продолжить бинарный поиск между текущей ценой p и максимальной ценой, чтобы получить следующие фрагменты.

Вот некоторый (грубый) псевдокод:

 search(startp, endp, threshold) {
    if (currency_round(startp) == currency_round(endp)) return startp;
    mid = startp   (endp - startp) / 2;
    count = get_prange_count(startp, mid);
    if (count == threshold) return mid;
    if (count > threshold)
        return search(startp, mid, threshold);
    // else count < threshold
    return search(mid, endp, threshold - count);
}
  
 

Временная сложность — это O(log max) где max максимальная цена.