Решён
Как распределить предметы между диапазонами чисел в Python?

ТихийМатематик • Python •
1.3k
4

Есть список предметов с весами:

items = [
  {'name': 'item1', 'weight': 45},
  {'name': 'item2', 'weight': 12},
  {'name': 'item3', 'weight': 78},
  {'name': 'item4', 'weight': 23},
  {'name': 'item5', 'weight': 91}
]

Есть диапазоны:

ranges = [(0, 50), (51, 100)]

Надо распределить предметы по диапазонам так чтобы вес каждого предмета попадал в свой диапазон. Как распределить предметы между диапазонами правильно?

PythonАлгоритмыСортировкаСписки

4 ответа

Лучшие Новые Старые
Решение
40
Участник • 2 ответа 
def distribute_items(items, ranges):
    result = {i: [] for i in range(len(ranges))}

    for item in items:
        weight = item['weight']
        for idx, (min_val, max_val) in enumerate(ranges):
            if min_val <= weight <= max_val:
                result[idx].append(item)
                break

    return result

result = distribute_items(items, ranges)
for idx, items_list in result.items():
    print(f"Range {ranges[idx]}: {items_list}")

Вывод:

Range (0, 50): [{'name': 'item1', 'weight': 45}, {'name': 'item2', 'weight': 12}, {'name': 'item4', 'weight': 23}]
Range (51, 100): [{'name': 'item3', 'weight': 78}, {'name': 'item5', 'weight': 91}]
Аватар ТихийМатематик
ТихийМатематик Автор

Спасибо, работает! Только у меня есть предметы которые не попадают ни в один диапазон, как их обработать?

Аватар Виктор Петров
Виктор Петров

Добавь отдельный ключ в словарь result для таких предметов. Например result['unmatched'] = []. И если предмет не попал ни в один диапазон, кидай его туда.

18
Участник • 2 ответа

А если диапазонов тысячи? Твое решение O(n*m) где n - предметы, m - диапазоны.

Лучше отсортировать диапазоны и использовать бинарный поиск. Сложность будет O(n log m).

import bisect

def distribute_optimized(items, ranges):
    sorted_ranges = sorted(ranges, key=lambda x: x[0])
    starts = [r[0] for r in sorted_ranges]
    result = {i: [] for i in range(len(ranges))}

    for item in items:
        weight = item['weight']
        idx = bisect.bisect_right(starts, weight) - 1
        if idx >= 0 and sorted_ranges[idx][0] <= weight <= sorted_ranges[idx][1]:
            result[idx].append(item)

    return result

Для маленьких датасетов разницы не будет, но если масштабируешь - вот тебе оптимизация.

Написать ответ

Визуальный редактор (WYSIWYG)
Премодерация гостей

Вы отвечаете как гость. Ваш ответ будет скрыт до проверки модератором. Чтобы ответ появился сразу и вы получали репутацию — войдите в аккаунт.

Или войдите в систему
Будьте вежливы и соблюдайте правила платформы.