python - 字典列表中第一次出现的二进制搜索

Question

所以我正在处理大型数据集，n>1000000。数据包含有关商品的订单信息。 JSON 格式的订单中有一个名为 is_buy_order 的 bool 值。我想将订单列表分成两个单独的列表，具体取决于 bool 值是 true 还是 false。

我想出了一个有缺陷但比迭代更快的算法。

该算法通过选择一个枢轴将数据集一分为二，然后检查任一侧以确定哪一侧更接近过渡点(false -> true) .它继续减半，直到枢轴两侧的值不同或 pivot == 1 表示没有变化。

start = time.time()
orders_file = open("resources/regions/"+x.replace(" ", "")[1:-1]+".json", 'r')
orders = orders_file.readlines()
orders_file.close()


item_buy, item_sell = [], []

pivot_found = False
print(len(orders))

if len(orders) > 1:
    while not pivot_found:
        temp_orders = orders
        pivot = len(temp_orders)//2

        if pivot == 1:
            break

        if json.loads(orders[pivot].replace("\n", ""))["is_buy_order"]:
            orders = orders[:pivot]
            buy_sell_index -= pivot
        else:
            orders = orders[pivot:]

        if json.loads(temp_orders[pivot].replace("\n", ""))["is_buy_order"] != json.loads(temp_orders[pivot-1].replace("\n", ""))["is_buy_order"]:
            pivot_found = True


item_buy, item_sell = temp_orders[:pivot], temp_orders[pivot:]
buy_sell_index = orders.index(item_sell[0])
print(x, time.time()-start, buy_sell_index) 

下面是一个严重缩减的数据集的内容:

{"duration":90,"is_buy_order":false,"issued":"2018-06-09T01:52:42Z","location_id":1027547438558,"min_volume":1,"order_id":5180297455,"price":16000.0,"range":"40","system_id":30001811,"type_id":28362,"volume_remain":892,"volume_total":892}
{"duration":90,"is_buy_order":false,"issued":"2018-06-09T01:53:11Z","location_id":1027547438558,"min_volume":1,"order_id":5180297673,"price":100000.0,"range":"40","system_id":30001811,"type_id":28366,"volume_remain":907,"volume_total":907}
{"duration":90,"is_buy_order":false,"issued":"2018-06-09T01:53:42Z","location_id":1027547438558,"min_volume":1,"order_id":5180297903,"price":100000.0,"range":"40","system_id":30001811,"type_id":21815,"volume_remain":906,"volume_total":906}
{"duration":90,"is_buy_order":true,"issued":"2018-08-03T01:50:59Z","location_id":1027954902335,"min_volume":1,"order_id":5191398100,"price":4.0,"range":"5","system_id":30001780,"type_id":34,"volume_remain":10000000,"volume_total":10000000}
{"duration":90,"is_buy_order":true,"issued":"2018-08-05T07:30:18Z","location_id":1028168079013,"min_volume":1,"order_id":5221892906,"price":2250000.0,"range":"4","system_id":30001748,"type_id":25615,"volume_remain":100,"volume_total":100}
{"duration":90,"is_buy_order":true,"issued":"2018-07-21T05:23:37Z","location_id":1022958758740,"min_volume":1,"order_id":5211030090,"price":185.0,"range":"5","system_id":30001786,"type_id":204,"volume_remain":40000,"volume_total":40000}
{"duration":90,"is_buy_order":true,"issued":"2018-08-05T07:31:23Z","location_id":1028168079013,"min_volume":1,"order_id":5221893610,"price":6000.0,"range":"4","system_id":30001748,"type_id":25616,"volume_remain":1000,"volume_total":1000}
{"duration":90,"is_buy_order":true,"issued":"2018-08-05T07:27:50Z","location_id":1028168079013,"min_volume":1,"order_id":5221891669,"price":1150000.0,"range":"4","system_id":30001748,"type_id":25619,"volume_remain":200,"volume_total":200}
{"duration":90,"is_buy_order":true,"issued":"2018-07-22T17:46:06Z","location_id":1022958758740,"min_volume":1,"order_id":5212328909,"price":12.0,"range":"5","system_id":30001786,"type_id":211,"volume_remain":1000000,"volume_total":1000000}
{"duration":30,"is_buy_order":true,"issued":"2018-07-19T22:18:58Z","location_id":1028168079013,"min_volume":1,"order_id":5210158811,"price":2000000.0,"range":"5","system_id":30001748,"type_id":16278,"volume_remain":3,"volume_total":3}
{"duration":90,"is_buy_order":true,"issued":"2018-08-05T07:32:18Z","location_id":1028168079013,"min_volume":1,"order_id":5221894118,"price":65000.0,"range":"4","system_id":30001748,"type_id":25606,"volume_remain":1000,"volume_total":1000}

如果数据集需要新的格式来实现这一点是有可能的。

Answer 1

bisect 模块有一种方法可以做到这一点。就其本身而言，它不支持关键功能，但您可以在您的列表周围添加一个包装器:

from bisect import bisect

my_list = [
    {"is_buy_order": False},
    {"is_buy_order": False},
    {"is_buy_order": False},
    {"is_buy_order": False},
    {"is_buy_order": True},
    {"is_buy_order": True},
    {"is_buy_order": True},
    {"is_buy_order": True},
    {"is_buy_order": True},
    {"is_buy_order": True}
]


class KeyFuncWrapper(object):
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __len__(self):
        return len(self.it)

    def __getitem__(self, i):
        return self.key(self.it[i])


# prints 4
print(bisect(
    KeyFuncWrapper(my_list, lambda x: x["is_buy_order"]),
    False,  # value for bisect to look for
))

这是有效的，因为 bisect 将查看 KeyFuncWrapper 的第 i 个元素，它本身会查看键函数在列表的第 i 个元素上的应用。