SortedCollection vs SortedContainers

[Scholastik]

Hallo,

Ziel ist es eine Liste dieser Art:
[[0, 2], [1, 2], [2, 2], [3, 2], [4, 2], [5, 2], [6, 2], [7, 2], [8, 2], [9, 2], [10, 2], [11, 2]...]
mit bis zu 10.000 Einträgen möglichst effizient sortiert zu haben (in dem beispiel nach entry[0]) und zu verändern, also Einträge löschen, oder entry[1] eines eintrags zu ändern, oder auch einträge hinzufügen/zwischenschieben (weiterhin sortiert),

Bisher verwende ich dafür "SortedCollection":
http://code.activestate.com/recipes/577 ... ollection/

Beispielcode:

Code: Alles auswählen

from SortedCollection import SortedCollection

def key_fkt(item):
    return item[0] 
        
def sortedtest():
    testliste = [[0, 2], [1, 2], [2, 2], [3, 2], [4, 2], [5, 2], [6, 2], [7, 2], [8, 2], [9, 2], [10, 2], [11, 2], [12, 2], [13, 2], [14, 2], [15, 2], [16, 2], [17, 2], [18, 2], [19, 2], [20, 2], [21, 2], [22, 2], [23, 2], [24, 2], [25, 2], [26, 2], [27, 2], [28, 2], [29, 2], [30, 2], [31, 2], [32, 2], [33, 2], [34, 2], [35, 2], [36, 2], [37, 2], [38, 2], [39, 2], [40, 2], [41, 2], [42, 2], [43, 2], [44, 2], [45, 2], [46, 2], [47, 2], [48, 2], [49, 2], [50, 2], [51, 2], [52, 2], [53, 2], [54, 2], [55, 2], [56, 2], [57, 2], [58, 2], [59, 2], [60, 2], [61, 2], [62, 2], [63, 2], [64, 2], [65, 2], [66, 2], [67, 2], [68, 2], [69, 2], [70, 2], [71, 2], [72, 2], [73, 2], [74, 2], [75, 2], [76, 2], [77, 2], [78, 2], [79, 2], [80, 2], [81, 2], [82, 2], [83, 2], [84, 2], [85, 2], [86, 2], [87, 2], [88, 2], [89, 2], [90, 2], [91, 2], [92, 2], [93, 2], [94, 2], [95, 2], [96, 2], [97, 2], [98, 2], [99, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2], [105, 2], [106, 2], [107, 2], [108, 2], [109, 2], [110, 2], [111, 2], [112, 2], [113, 2], [114, 2], [115, 2], [116, 2], [117, 2], [118, 2], [119, 2], [120, 2], [121, 2], [122, 2], [123, 2], [124, 2], [125, 2], [126, 2], [127, 2], [128, 2], [129, 2], [130, 2], [131, 2], [132, 2], [133, 2], [134, 2], [135, 2], [136, 2], [137, 2], [138, 2], [139, 2], [140, 2], [141, 2], [142, 2], [143, 2], [144, 2], [145, 2], [146, 2], [147, 2], [148, 2], [149, 2], [150, 2], [151, 2], [152, 2], [153, 2], [154, 2], [155, 2], [156, 2], [157, 2], [158, 2], [159, 2], [160, 2], [161, 2], [162, 2], [163, 2], [164, 2], [165, 2], [166, 2], [167, 2], [168, 2], [169, 2], [170, 2], [171, 2], [172, 2], [173, 2], [174, 2], [175, 2], [176, 2], [177, 2], [178, 2], [179, 2], [180, 2], [181, 2], [182, 2], [183, 2], [184, 2], [185, 2], [186, 2], [187, 2], [188, 2], [189, 2], [190, 2], [191, 2], [192, 2], [193, 2], [194, 2], [195, 2], [196, 2], [197, 2], [198, 2], [199, 2], [200, 2], [201, 2], [202, 2], [203, 2], [204, 2], [205, 2], [206, 2], [207, 2], [208, 2], [209, 2], [210, 2], [211, 2], [212, 2], [213, 2], [214, 2], [215, 2], [216, 2], [217, 2], [218, 2], [219, 2], [220, 2], [221, 2], [222, 2], [223, 2], [224, 2], [225, 2], [226, 2], [227, 2], [228, 2], [229, 2], [230, 2], [231, 2], [232, 2], [233, 2], [234, 2], [235, 2], [236, 2], [237, 2], [238, 2], [239, 2], [240, 2], [241, 2], [242, 2], [243, 2], [244, 2], [245, 2], [246, 2], [247, 2], [248, 2], [249, 2], [250, 2], [251, 2], [252, 2], [253, 2], [254, 2], [255, 2], [256, 2], [257, 2], [258, 2], [259, 2], [260, 2], [261, 2], [262, 2], [263, 2], [264, 2], [265, 2], [266, 2], [267, 2], [268, 2], [269, 2], [270, 2], [271, 2], [272, 2], [273, 2], [274, 2], [275, 2], [276, 2], [277, 2], [278, 2], [279, 2], [280, 2], [281, 2], [282, 2], [283, 2], [284, 2], [285, 2], [286, 2], [287, 2], [288, 2], [289, 2], [290, 2], [291, 2], [292, 2], [293, 2], [294, 2], [295, 2], [296, 2], [297, 2], [298, 2], [299, 2], [300, 2], [301, 2], [302, 2], [303, 2], [304, 2], [305, 2], [306, 2], [307, 2], [308, 2], [309, 2], [310, 2], [311, 2], [312, 2], [313, 2], [314, 2], [315, 2], [316, 2], [317, 2], [318, 2], [319, 2], [320, 2], [321, 2], [322, 2], [323, 2], [324, 2], [325, 2], [326, 2], [327, 2], [328, 2], [329, 2], [330, 2], [331, 2], [332, 2], [333, 2], [334, 2], [335, 2], [336, 2], [337, 2], [338, 2], [339, 2], [340, 2], [341, 2], [342, 2], [343, 2], [344, 2], [345, 2], [346, 2], [347, 2], [348, 2], [349, 2], [350, 2], [351, 2], [352, 2], [353, 2], [354, 2], [355, 2], [356, 2], [357, 2], [358, 2], [359, 2], [360, 2], [361, 2], [362, 2], [363, 2], [364, 2], [365, 2], [366, 2], [367, 2], [368, 2], [369, 2], [370, 2], [371, 2], [372, 2], [373, 2], [374, 2], [375, 2], [376, 2], [377, 2], [378, 2], [379, 2], [380, 2], [381, 2], [382, 2], [383, 2], [384, 2], [385, 2], [386, 2], [387, 2], [388, 2], [389, 2], [390, 2], [391, 2], [392, 2], [393, 2], [394, 2], [395, 2], [396, 2], [397, 2], [398, 2], [399, 2], [400, 2], [401, 2], [402, 2], [403, 2], [404, 2], [405, 2], [406, 2], [407, 2], [408, 2], [409, 2], [410, 2], [411, 2], [412, 2], [413, 2], [414, 2], [415, 2], [416, 2], [417, 2], [418, 2], [419, 2], [420, 2], [421, 2], [422, 2], [423, 2], [424, 2], [425, 2], [426, 2], [427, 2], [428, 2], [429, 2], [430, 2], [431, 2], [432, 2], [433, 2], [434, 2], [435, 2], [436, 2], [437, 2], [438, 2], [439, 2], [440, 2], [441, 2], [442, 2], [443, 2], [444, 2], [445, 2], [446, 2], [447, 2], [448, 2], [449, 2], [450, 2], [451, 2], [452, 2], [453, 2], [454, 2], [455, 2], [456, 2], [457, 2], [458, 2], [459, 2], [460, 2], [461, 2], [462, 2], [463, 2], [464, 2], [465, 2], [466, 2], [467, 2], [468, 2], [469, 2], [470, 2], [471, 2], [472, 2], [473, 2], [474, 2], [475, 2], [476, 2], [477, 2], [478, 2], [479, 2], [480, 2], [481, 2], [482, 2], [483, 2], [484, 2], [485, 2], [486, 2], [487, 2], [488, 2], [489, 2], [490, 2], [491, 2], [492, 2], [493, 2], [494, 2], [495, 2], [496, 2], [497, 2], [498, 2], [499, 2], [500, 2], [501, 2], [502, 2], [503, 2], [504, 2], [505, 2], [506, 2], [507, 2], [508, 2], [509, 2], [510, 2], [511, 2], [512, 2], [513, 2], [514, 2], [515, 2], [516, 2], [517, 2], [518, 2], [519, 2], [520, 2], [521, 2], [522, 2], [523, 2], [524, 2], [525, 2], [526, 2], [527, 2], [528, 2], [529, 2], [530, 2], [531, 2], [532, 2], [533, 2], [534, 2], [535, 2], [536, 2], [537, 2], [538, 2], [539, 2], [540, 2], [541, 2], [542, 2], [543, 2], [544, 2], [545, 2], [546, 2], [547, 2], [548, 2], [549, 2], [550, 2], [551, 2], [552, 2], [553, 2], [554, 2], [555, 2], [556, 2], [557, 2], [558, 2], [559, 2], [560, 2], [561, 2], [562, 2], [563, 2], [564, 2], [565, 2], [566, 2], [567, 2], [568, 2], [569, 2], [570, 2], [571, 2], [572, 2], [573, 2], [574, 2], [575, 2], [576, 2], [577, 2], [578, 2], [579, 2], [580, 2], [581, 2], [582, 2], [583, 2], [584, 2], [585, 2], [586, 2], [587, 2], [588, 2], [589, 2], [590, 2], [591, 2], [592, 2], [593, 2], [594, 2], [595, 2], [596, 2], [597, 2], [598, 2], [599, 2], [600, 2], [601, 2], [602, 2], [603, 2], [604, 2], [605, 2], [606, 2], [607, 2], [608, 2], [609, 2], [610, 2], [611, 2], [612, 2], [613, 2], [614, 2], [615, 2], [616, 2], [617, 2], [618, 2], [619, 2], [620, 2], [621, 2], [622, 2], [623, 2], [624, 2], [625, 2], [626, 2], [627, 2], [628, 2], [629, 2], [630, 2], [631, 2], [632, 2], [633, 2], [634, 2], [635, 2], [636, 2], [637, 2], [638, 2], [639, 2], [640, 2], [641, 2], [642, 2], [643, 2], [644, 2], [645, 2], [646, 2], [647, 2], [648, 2], [649, 2], [650, 2], [651, 2], [652, 2], [653, 2], [654, 2], [655, 2], [656, 2], [657, 2], [658, 2], [659, 2], [660, 2], [661, 2], [662, 2], [663, 2], [664, 2], [665, 2], [666, 2], [667, 2], [668, 2], [669, 2], [670, 2], [671, 2], [672, 2], [673, 2], [674, 2], [675, 2], [676, 2], [677, 2], [678, 2], [679, 2], [680, 2], [681, 2], [682, 2], [683, 2], [684, 2], [685, 2], [686, 2], [687, 2], [688, 2], [689, 2], [690, 2], [691, 2], [692, 2], [693, 2], [694, 2], [695, 2], [696, 2], [697, 2], [698, 2], [699, 2], [700, 2], [701, 2], [702, 2], [703, 2], [704, 2], [705, 2], [706, 2], [707, 2], [708, 2], [709, 2], [710, 2], [711, 2], [712, 2], [713, 2], [714, 2], [715, 2], [716, 2], [717, 2], [718, 2], [719, 2], [720, 2], [721, 2], [722, 2], [723, 2], [724, 2], [725, 2], [726, 2], [727, 2], [728, 2], [729, 2], [730, 2], [731, 2], [732, 2], [733, 2], [734, 2], [735, 2], [736, 2], [737, 2], [738, 2], [739, 2], [740, 2], [741, 2], [742, 2], [743, 2], [744, 2], [745, 2], [746, 2], [747, 2], [748, 2], [749, 2], [750, 2], [751, 2], [752, 2], [753, 2], [754, 2], [755, 2], [756, 2], [757, 2], [758, 2], [759, 2], [760, 2], [761, 2], [762, 2], [763, 2], [764, 2], [765, 2], [766, 2], [767, 2], [768, 2], [769, 2], [770, 2], [771, 2], [772, 2], [773, 2], [774, 2], [775, 2], [776, 2], [777, 2], [778, 2], [779, 2], [780, 2], [781, 2], [782, 2], [783, 2], [784, 2], [785, 2], [786, 2], [787, 2], [788, 2], [789, 2], [790, 2], [791, 2], [792, 2], [793, 2], [794, 2], [795, 2], [796, 2], [797, 2], [798, 2], [799, 2], [800, 2], [801, 2], [802, 2], [803, 2], [804, 2], [805, 2], [806, 2], [807, 2], [808, 2], [809, 2], [810, 2], [811, 2], [812, 2], [813, 2], [814, 2], [815, 2], [816, 2], [817, 2], [818, 2], [819, 2], [820, 2], [821, 2], [822, 2], [823, 2], [824, 2], [825, 2], [826, 2], [827, 2], [828, 2], [829, 2], [830, 2], [831, 2], [832, 2], [833, 2], [834, 2], [835, 2], [836, 2], [837, 2], [838, 2], [839, 2], [840, 2], [841, 2], [842, 2], [843, 2], [844, 2], [845, 2], [846, 2], [847, 2], [848, 2], [849, 2], [850, 2], [851, 2], [852, 2], [853, 2], [854, 2], [855, 2], [856, 2], [857, 2], [858, 2], [859, 2], [860, 2], [861, 2], [862, 2], [863, 2], [864, 2], [865, 2], [866, 2], [867, 2], [868, 2], [869, 2], [870, 2], [871, 2], [872, 2], [873, 2], [874, 2], [875, 2], [876, 2], [877, 2], [878, 2], [879, 2], [880, 2], [881, 2], [882, 2], [883, 2], [884, 2], [885, 2], [886, 2], [887, 2], [888, 2], [889, 2], [890, 2], [891, 2], [892, 2], [893, 2], [894, 2], [895, 2], [896, 2], [897, 2], [898, 2], [899, 2], [900, 2], [901, 2], [902, 2], [903, 2], [904, 2], [905, 2], [906, 2], [907, 2], [908, 2], [909, 2], [910, 2], [911, 2], [912, 2], [913, 2], [914, 2], [915, 2], [916, 2], [917, 2], [918, 2], [919, 2], [920, 2], [921, 2], [922, 2], [923, 2], [924, 2], [925, 2], [926, 2], [927, 2], [928, 2], [929, 2], [930, 2], [931, 2], [932, 2], [933, 2], [934, 2], [935, 2], [936, 2], [937, 2], [938, 2], [939, 2], [940, 2], [941, 2], [942, 2], [943, 2], [944, 2], [945, 2], [946, 2], [947, 2], [948, 2], [949, 2], [950, 2], [951, 2], [952, 2], [953, 2], [954, 2], [955, 2], [956, 2], [957, 2], [958, 2], [959, 2], [960, 2], [961, 2], [962, 2], [963, 2], [964, 2], [965, 2], [966, 2], [967, 2], [968, 2], [969, 2], [970, 2], [971, 2], [972, 2], [973, 2], [974, 2], [975, 2], [976, 2], [977, 2], [978, 2], [979, 2], [980, 2], [981, 2], [982, 2], [983, 2], [984, 2], [985, 2], [986, 2], [987, 2], [988, 2], [989, 2], [990, 2], [991, 2], [992, 2], [993, 2], [994, 2], [995, 2], [996, 2], [997, 2], [998, 2], [999, 2]]
    s = SortedCollection(testliste,key=key_fkt)
    for i in range(1000000):
        item = s.find(5)

Die Ausführung dieser sortedtest fkt dauert bei mir ca. 1 sekunde.

Nun ist das Problem, dass dies leider noch zu langsam ist. Auf der Suche nach schnelleren Möglichkeiten, stieß ich auf Cython. Weiteres googlen brachte mich allerdings auf SortedContainers, welches hier hochgelobt wird und behauptet sogar mit C mithalten zu können, ohne Cython zu benötigen: http://www.grantjenks.com/docs/sortedcontainers

Nun hat sortedcontainers scheinbar keine solche "find()" funktion, weshalb ich mal annehme, dass ich erst den index suchen und dann diesen aufrufen muss? Ein Beispielcode der erstmal nur den index findet sähe dann so aus:

Code: Alles auswählen

import sortedcontainers

def sortedtest2():
    testliste = [[0, 2], [1, 2], [2, 2], [3, 2], [4, 2], [5, 2], [6, 2], [7, 2], [8, 2], [9, 2], [10, 2], [11, 2], [12, 2], [13, 2], [14, 2], [15, 2], [16, 2], [17, 2], [18, 2], [19, 2], [20, 2], [21, 2], [22, 2], [23, 2], [24, 2], [25, 2], [26, 2], [27, 2], [28, 2], [29, 2], [30, 2], [31, 2], [32, 2], [33, 2], [34, 2], [35, 2], [36, 2], [37, 2], [38, 2], [39, 2], [40, 2], [41, 2], [42, 2], [43, 2], [44, 2], [45, 2], [46, 2], [47, 2], [48, 2], [49, 2], [50, 2], [51, 2], [52, 2], [53, 2], [54, 2], [55, 2], [56, 2], [57, 2], [58, 2], [59, 2], [60, 2], [61, 2], [62, 2], [63, 2], [64, 2], [65, 2], [66, 2], [67, 2], [68, 2], [69, 2], [70, 2], [71, 2], [72, 2], [73, 2], [74, 2], [75, 2], [76, 2], [77, 2], [78, 2], [79, 2], [80, 2], [81, 2], [82, 2], [83, 2], [84, 2], [85, 2], [86, 2], [87, 2], [88, 2], [89, 2], [90, 2], [91, 2], [92, 2], [93, 2], [94, 2], [95, 2], [96, 2], [97, 2], [98, 2], [99, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2], [105, 2], [106, 2], [107, 2], [108, 2], [109, 2], [110, 2], [111, 2], [112, 2], [113, 2], [114, 2], [115, 2], [116, 2], [117, 2], [118, 2], [119, 2], [120, 2], [121, 2], [122, 2], [123, 2], [124, 2], [125, 2], [126, 2], [127, 2], [128, 2], [129, 2], [130, 2], [131, 2], [132, 2], [133, 2], [134, 2], [135, 2], [136, 2], [137, 2], [138, 2], [139, 2], [140, 2], [141, 2], [142, 2], [143, 2], [144, 2], [145, 2], [146, 2], [147, 2], [148, 2], [149, 2], [150, 2], [151, 2], [152, 2], [153, 2], [154, 2], [155, 2], [156, 2], [157, 2], [158, 2], [159, 2], [160, 2], [161, 2], [162, 2], [163, 2], [164, 2], [165, 2], [166, 2], [167, 2], [168, 2], [169, 2], [170, 2], [171, 2], [172, 2], [173, 2], [174, 2], [175, 2], [176, 2], [177, 2], [178, 2], [179, 2], [180, 2], [181, 2], [182, 2], [183, 2], [184, 2], [185, 2], [186, 2], [187, 2], [188, 2], [189, 2], [190, 2], [191, 2], [192, 2], [193, 2], [194, 2], [195, 2], [196, 2], [197, 2], [198, 2], [199, 2], [200, 2], [201, 2], [202, 2], [203, 2], [204, 2], [205, 2], [206, 2], [207, 2], [208, 2], [209, 2], [210, 2], [211, 2], [212, 2], [213, 2], [214, 2], [215, 2], [216, 2], [217, 2], [218, 2], [219, 2], [220, 2], [221, 2], [222, 2], [223, 2], [224, 2], [225, 2], [226, 2], [227, 2], [228, 2], [229, 2], [230, 2], [231, 2], [232, 2], [233, 2], [234, 2], [235, 2], [236, 2], [237, 2], [238, 2], [239, 2], [240, 2], [241, 2], [242, 2], [243, 2], [244, 2], [245, 2], [246, 2], [247, 2], [248, 2], [249, 2], [250, 2], [251, 2], [252, 2], [253, 2], [254, 2], [255, 2], [256, 2], [257, 2], [258, 2], [259, 2], [260, 2], [261, 2], [262, 2], [263, 2], [264, 2], [265, 2], [266, 2], [267, 2], [268, 2], [269, 2], [270, 2], [271, 2], [272, 2], [273, 2], [274, 2], [275, 2], [276, 2], [277, 2], [278, 2], [279, 2], [280, 2], [281, 2], [282, 2], [283, 2], [284, 2], [285, 2], [286, 2], [287, 2], [288, 2], [289, 2], [290, 2], [291, 2], [292, 2], [293, 2], [294, 2], [295, 2], [296, 2], [297, 2], [298, 2], [299, 2], [300, 2], [301, 2], [302, 2], [303, 2], [304, 2], [305, 2], [306, 2], [307, 2], [308, 2], [309, 2], [310, 2], [311, 2], [312, 2], [313, 2], [314, 2], [315, 2], [316, 2], [317, 2], [318, 2], [319, 2], [320, 2], [321, 2], [322, 2], [323, 2], [324, 2], [325, 2], [326, 2], [327, 2], [328, 2], [329, 2], [330, 2], [331, 2], [332, 2], [333, 2], [334, 2], [335, 2], [336, 2], [337, 2], [338, 2], [339, 2], [340, 2], [341, 2], [342, 2], [343, 2], [344, 2], [345, 2], [346, 2], [347, 2], [348, 2], [349, 2], [350, 2], [351, 2], [352, 2], [353, 2], [354, 2], [355, 2], [356, 2], [357, 2], [358, 2], [359, 2], [360, 2], [361, 2], [362, 2], [363, 2], [364, 2], [365, 2], [366, 2], [367, 2], [368, 2], [369, 2], [370, 2], [371, 2], [372, 2], [373, 2], [374, 2], [375, 2], [376, 2], [377, 2], [378, 2], [379, 2], [380, 2], [381, 2], [382, 2], [383, 2], [384, 2], [385, 2], [386, 2], [387, 2], [388, 2], [389, 2], [390, 2], [391, 2], [392, 2], [393, 2], [394, 2], [395, 2], [396, 2], [397, 2], [398, 2], [399, 2], [400, 2], [401, 2], [402, 2], [403, 2], [404, 2], [405, 2], [406, 2], [407, 2], [408, 2], [409, 2], [410, 2], [411, 2], [412, 2], [413, 2], [414, 2], [415, 2], [416, 2], [417, 2], [418, 2], [419, 2], [420, 2], [421, 2], [422, 2], [423, 2], [424, 2], [425, 2], [426, 2], [427, 2], [428, 2], [429, 2], [430, 2], [431, 2], [432, 2], [433, 2], [434, 2], [435, 2], [436, 2], [437, 2], [438, 2], [439, 2], [440, 2], [441, 2], [442, 2], [443, 2], [444, 2], [445, 2], [446, 2], [447, 2], [448, 2], [449, 2], [450, 2], [451, 2], [452, 2], [453, 2], [454, 2], [455, 2], [456, 2], [457, 2], [458, 2], [459, 2], [460, 2], [461, 2], [462, 2], [463, 2], [464, 2], [465, 2], [466, 2], [467, 2], [468, 2], [469, 2], [470, 2], [471, 2], [472, 2], [473, 2], [474, 2], [475, 2], [476, 2], [477, 2], [478, 2], [479, 2], [480, 2], [481, 2], [482, 2], [483, 2], [484, 2], [485, 2], [486, 2], [487, 2], [488, 2], [489, 2], [490, 2], [491, 2], [492, 2], [493, 2], [494, 2], [495, 2], [496, 2], [497, 2], [498, 2], [499, 2], [500, 2], [501, 2], [502, 2], [503, 2], [504, 2], [505, 2], [506, 2], [507, 2], [508, 2], [509, 2], [510, 2], [511, 2], [512, 2], [513, 2], [514, 2], [515, 2], [516, 2], [517, 2], [518, 2], [519, 2], [520, 2], [521, 2], [522, 2], [523, 2], [524, 2], [525, 2], [526, 2], [527, 2], [528, 2], [529, 2], [530, 2], [531, 2], [532, 2], [533, 2], [534, 2], [535, 2], [536, 2], [537, 2], [538, 2], [539, 2], [540, 2], [541, 2], [542, 2], [543, 2], [544, 2], [545, 2], [546, 2], [547, 2], [548, 2], [549, 2], [550, 2], [551, 2], [552, 2], [553, 2], [554, 2], [555, 2], [556, 2], [557, 2], [558, 2], [559, 2], [560, 2], [561, 2], [562, 2], [563, 2], [564, 2], [565, 2], [566, 2], [567, 2], [568, 2], [569, 2], [570, 2], [571, 2], [572, 2], [573, 2], [574, 2], [575, 2], [576, 2], [577, 2], [578, 2], [579, 2], [580, 2], [581, 2], [582, 2], [583, 2], [584, 2], [585, 2], [586, 2], [587, 2], [588, 2], [589, 2], [590, 2], [591, 2], [592, 2], [593, 2], [594, 2], [595, 2], [596, 2], [597, 2], [598, 2], [599, 2], [600, 2], [601, 2], [602, 2], [603, 2], [604, 2], [605, 2], [606, 2], [607, 2], [608, 2], [609, 2], [610, 2], [611, 2], [612, 2], [613, 2], [614, 2], [615, 2], [616, 2], [617, 2], [618, 2], [619, 2], [620, 2], [621, 2], [622, 2], [623, 2], [624, 2], [625, 2], [626, 2], [627, 2], [628, 2], [629, 2], [630, 2], [631, 2], [632, 2], [633, 2], [634, 2], [635, 2], [636, 2], [637, 2], [638, 2], [639, 2], [640, 2], [641, 2], [642, 2], [643, 2], [644, 2], [645, 2], [646, 2], [647, 2], [648, 2], [649, 2], [650, 2], [651, 2], [652, 2], [653, 2], [654, 2], [655, 2], [656, 2], [657, 2], [658, 2], [659, 2], [660, 2], [661, 2], [662, 2], [663, 2], [664, 2], [665, 2], [666, 2], [667, 2], [668, 2], [669, 2], [670, 2], [671, 2], [672, 2], [673, 2], [674, 2], [675, 2], [676, 2], [677, 2], [678, 2], [679, 2], [680, 2], [681, 2], [682, 2], [683, 2], [684, 2], [685, 2], [686, 2], [687, 2], [688, 2], [689, 2], [690, 2], [691, 2], [692, 2], [693, 2], [694, 2], [695, 2], [696, 2], [697, 2], [698, 2], [699, 2], [700, 2], [701, 2], [702, 2], [703, 2], [704, 2], [705, 2], [706, 2], [707, 2], [708, 2], [709, 2], [710, 2], [711, 2], [712, 2], [713, 2], [714, 2], [715, 2], [716, 2], [717, 2], [718, 2], [719, 2], [720, 2], [721, 2], [722, 2], [723, 2], [724, 2], [725, 2], [726, 2], [727, 2], [728, 2], [729, 2], [730, 2], [731, 2], [732, 2], [733, 2], [734, 2], [735, 2], [736, 2], [737, 2], [738, 2], [739, 2], [740, 2], [741, 2], [742, 2], [743, 2], [744, 2], [745, 2], [746, 2], [747, 2], [748, 2], [749, 2], [750, 2], [751, 2], [752, 2], [753, 2], [754, 2], [755, 2], [756, 2], [757, 2], [758, 2], [759, 2], [760, 2], [761, 2], [762, 2], [763, 2], [764, 2], [765, 2], [766, 2], [767, 2], [768, 2], [769, 2], [770, 2], [771, 2], [772, 2], [773, 2], [774, 2], [775, 2], [776, 2], [777, 2], [778, 2], [779, 2], [780, 2], [781, 2], [782, 2], [783, 2], [784, 2], [785, 2], [786, 2], [787, 2], [788, 2], [789, 2], [790, 2], [791, 2], [792, 2], [793, 2], [794, 2], [795, 2], [796, 2], [797, 2], [798, 2], [799, 2], [800, 2], [801, 2], [802, 2], [803, 2], [804, 2], [805, 2], [806, 2], [807, 2], [808, 2], [809, 2], [810, 2], [811, 2], [812, 2], [813, 2], [814, 2], [815, 2], [816, 2], [817, 2], [818, 2], [819, 2], [820, 2], [821, 2], [822, 2], [823, 2], [824, 2], [825, 2], [826, 2], [827, 2], [828, 2], [829, 2], [830, 2], [831, 2], [832, 2], [833, 2], [834, 2], [835, 2], [836, 2], [837, 2], [838, 2], [839, 2], [840, 2], [841, 2], [842, 2], [843, 2], [844, 2], [845, 2], [846, 2], [847, 2], [848, 2], [849, 2], [850, 2], [851, 2], [852, 2], [853, 2], [854, 2], [855, 2], [856, 2], [857, 2], [858, 2], [859, 2], [860, 2], [861, 2], [862, 2], [863, 2], [864, 2], [865, 2], [866, 2], [867, 2], [868, 2], [869, 2], [870, 2], [871, 2], [872, 2], [873, 2], [874, 2], [875, 2], [876, 2], [877, 2], [878, 2], [879, 2], [880, 2], [881, 2], [882, 2], [883, 2], [884, 2], [885, 2], [886, 2], [887, 2], [888, 2], [889, 2], [890, 2], [891, 2], [892, 2], [893, 2], [894, 2], [895, 2], [896, 2], [897, 2], [898, 2], [899, 2], [900, 2], [901, 2], [902, 2], [903, 2], [904, 2], [905, 2], [906, 2], [907, 2], [908, 2], [909, 2], [910, 2], [911, 2], [912, 2], [913, 2], [914, 2], [915, 2], [916, 2], [917, 2], [918, 2], [919, 2], [920, 2], [921, 2], [922, 2], [923, 2], [924, 2], [925, 2], [926, 2], [927, 2], [928, 2], [929, 2], [930, 2], [931, 2], [932, 2], [933, 2], [934, 2], [935, 2], [936, 2], [937, 2], [938, 2], [939, 2], [940, 2], [941, 2], [942, 2], [943, 2], [944, 2], [945, 2], [946, 2], [947, 2], [948, 2], [949, 2], [950, 2], [951, 2], [952, 2], [953, 2], [954, 2], [955, 2], [956, 2], [957, 2], [958, 2], [959, 2], [960, 2], [961, 2], [962, 2], [963, 2], [964, 2], [965, 2], [966, 2], [967, 2], [968, 2], [969, 2], [970, 2], [971, 2], [972, 2], [973, 2], [974, 2], [975, 2], [976, 2], [977, 2], [978, 2], [979, 2], [980, 2], [981, 2], [982, 2], [983, 2], [984, 2], [985, 2], [986, 2], [987, 2], [988, 2], [989, 2], [990, 2], [991, 2], [992, 2], [993, 2], [994, 2], [995, 2], [996, 2], [997, 2], [998, 2], [999, 2]]
    s = sortedcontainers.SortedList(testliste)
    for i in range(1000000):
        index = s.index([5,2])

1) Allein nur das finden des Index, ohne auf das eigentliche item zu kommen, dauert bereits 1.5 sekunden.
2) Es gibt hier noch keine key funktion. Dafür kann man wohl SortedList durch "SortedKeyList" ersetzen und als key die key_fkt übergeben. Allerdings scheint diese lediglich für Sortierung relevant zu sein. Eine direkte Suche ala "find(5)", welches den eintrag mit key 5 finden würde, gibt es so direkt nicht. Sicherlich kann man sich das irgendwie noch selbst basteln.

Aber da allein das suchen nach dem index schon soviel länger braucht, frage ich mich woran das liegt, bzw ob sortedlist tatsächlich schlechter als sortedcollection ist?
Oder wie könnte ich das Prozedere sonst noch beschleunigen?

[__deets__]

Du suchst linear. Das ist bei sortierten Daten völlig unnötig. Benutz zb das bisect Modul, um auch mit einer normalen sortierten Liste schneller zu suchen. ABER: etwas 1000000 mal zu machen dauert halt. Da kannst du in Python dann schlussendlich keine Wunder erwarten. Dann ist der Rückgriff auf C/C++ angeraten.

[Scholastik]

Du suchst linear. Das ist bei sortierten Daten völlig unnötig. Benutz zb das bisect Modul, um auch mit einer normalen sortierten Liste schneller zu suchen. ABER: etwas 1000000 mal zu machen dauert halt. Da kannst du in Python dann schlussendlich keine Wunder erwarten. Dann ist der Rückgriff auf C/C++ angeraten.

Hi, danke für deine Antwort

Ich nehme mal an das linear quasi das Gegenstück zu binär<->bisect ist? SortedCollection find() verwendet bisect und ich geh mal stark davon aus, dass sortedContainers das auch tut? Wobei, könnte sein, dass index() das nicht nimmt (hab jetzt nicht in den Code geschaut). Ersetze ich .index() durch .bisect_left() was ja auch bestandteil der sortedcontainers ist, dann komme ich immerhin auf 1.2 sekunden, ist zwar schneller, reicht aber immernoch nicht an sortedCollection ran.


Es ist mir völlig klar, dass so ein Prozedere lange dauert.
Hier möchte ich nun die Möglichkeiten besprechen wie es am schnellsten geht, angesprochen habe ich ja bereits sortedCollection, sortedContainer und Cython hab ich ja auch kurz erwähnt.

Könnt ihr also bestätigen, dass SortedContainer in diesem Anwendungsfall keinerlei Vorteile gegenüber SortedCollection hat, oder wende ich es schlicht falsch an? Wie SortedCollection funktioniert weiß ich, da der code ja doch recht einfach und übersichtlich gehalten ist. Wie SortedContainers funktioniert hab ich mir nicht angeschaut, da es ja über pip installiert wird (kann mir aber vorstellen, dass es nicht gerade leicht verständlich geschrieben ist, denn auch die Doku ist nicht gerade einfach )

Und wenn es mit diesen 2 Möglichkeiten und auch Python allgemein keine weitere Optimierungsmöglichkeit mehr gibt, kommen wir zu C, bzw Cython.
Kann man den sortedCollection Code verbessern, sodass er als .pyx Datei mithilfe von Cython schneller werden wird? Cython hab ich bisher nur ein Basic Tutorial gelesen und es soll wohl recht kompliziert werden, wenn es um arrays geht. Und sortedCollection besteht ja eig zum Großteil nur aus 2 Listen (items und keys)

[noisefloor]

Hallo,

was man zur Steigerung der Geschwindigkeit immer einfach und schnell testen kann:

* Programm unter PyPy laufen lassen
* die zu beschleunigende Funktion mit dem JIT-Compiler aus Numba dekorieren

Gruß, noisefloor

[Sirius3]

@Scholastik: was ist denn Dein eigentliches Problem? Das hört sich doch recht akademisch an. Bei 1Mio mal den selben Index zu suchen, würde ich sagen, mach das einmal, dann bist Du schneller. Und genauso ist es mit Deinem Problem, das wir nicht kennen, und daher auch gar nicht sagen können, welche Datenstruktur jetzt die richtige ist.
Wenn Du sehr viele Zugriffe hast, dann ist ein Wörterbuch die richtige Datenstruktur. Bisher brauchst Du die sortierte Reihenfolge doch gar nicht.

An abstrakten Beispielen Optimierungen vorzunehmen, ist unsinnig. bisect ist schon in C geschrieben, da mit einer anderen Methode noch mehr Geschwindigkeit zu erhoffen, ist leicht optimistisch.

Ohne das Problem zu kennen, ist Helfen nicht möglich. Nach bisherigem Stand: nimm ein Wörterbuch.

[__deets__]

Es war spät gestern, ich bin davon ausgegangen, dass das find dem der Listen in Python entspricht. Das eben keine Annahmen über eine vorhandene Ordnung macht.

Aber das Rezept tut ja genau das. Insofern kann das nicht substantiell zur verschnellerung beitragen. Gleiches gilt für SortedContainers

Die Möglichkeiten, das zu verschnellern, sind begrenzt:

- weniger CPU Zyklen benutzen
- mehr Cache Nutzung

Für ersteres sind Cython und PyPy Kandidaten. Für letzteres kannst du nur numpy benutzen. https://docs.scipy.org/doc/numpy-1.15.0 ... orted.html

[Scholastik]

Zum Thema um das es geht:

Es geht um Aufrechterhaltung eines real time orderbooks. entry[0] ist in diesem Beispiel der Preis und entry[1] die Menge, weshalb die Liste nach entry[0] also dem Preis sortiert sein muss.
Ich bekomme zu beginn einen snapshot und danach in 35ms abständen updates zu dem orderbook. Und das ganze soll gleichzeitig für ~400 orderbooks funktionieren, also im höchstfall 400 updates alle 35ms. (aktuell ist mein skript dafür nicht schnell genug und es kommen schneller updates rein, als sie verarbietet werden können). Ein update enthält in der Regel nur eine oder eine handvoll Neuerungen, aber es kommen halt sehr viele in kurzer Zeit.
Dabei muss ich, wie bereits im Eingangspost erwähnt, das vorhandene orderbook updaten, also entweder die menge ändern, oder eine preisklasse entfernen (alternativ menge 0 setzen, aber dann könnte die Liste unendlich groß werden), bzw Preisklassen zwischenfügen, falls es sie noch nicht gibt.
Der Beispielcode ist lediglich ein Test um zu testen, was wie schnell ist.

Danke für die weiteren Vorschläge.
Aber könntet ihr vielleicht etwas weiter gehen und mir konkreter zeigen was zu zun ist? Ich meine ihr habt den kompletten sourcecode von sortedCollection. Wenn das nun zb mit cython beschleunigt werden kann, dann zeigt mir bitte wie ich den sortedcollection Code ändern muss, damit er durch cython schneller wird, denn ihn einfach nur mit cython auszuführen, verschnellert ihn leider nicht wirklich (genauso für Pypy, was ich noch nicht ausprobiert habe, falls da irgendwelche Anpassungem im Cod nötig sein sollten)

edit:
Hier mal mein code, wie ein update im tatsächlichen script (mit sortedcollection) verarbeitet wird:

Code: Alles auswählen

try:
    item = self._orderbook[symbol]["bids"].find(preis)
except ValueError as valueerror: # dann gibts den eintrag noch nicht
    item = False
    if menge!=0:
        self._orderbook[symbol]["bids"].insert([preis,menge])
if item: # dann gabs den eintrag    
    if menge!=0:
        item[2] = menge # menge updaten
    else:# ist 0, dann entfernen
        self._orderbook[symbol]["bids"].remove(item)

das einzige was man hier wohl verbessern koennte, wäre wohl auf remove zu verzichten, was insg auch seltener insert verlangen würde. Nur kann es dadurch potentiell unendlich groß werden, wobei man dies loesen könnte, indem man zb alle paar Stunden von vorne anfängt und einen neuen snapshot anfordert. Dennoch ist es weiterhin nicht schnell genug.

[__deets__]

Wenn du pypy nicht probiert hast, dann mach das mal. Da sollten erstmal keine Aenderungen notwendig sein. ACHTUNG: pypy hat einen JIT, der erstmal "warm" werden muss, d.h. verbesserungen stellen sich erst nach einer gewissen Laufzeit ein!

Wenn das nicht die gewuenschte Verbesserung erzielt, dann musst du in den sauren Apfel beissen. Und ich prognostiziere: das wird passieren. Denn 35ms/400 sind ca 80 Microsekunden pro Order. Wenn da etwas passieren soll, dann ist Python aller Wahrscheinlichkeit immer zu langsam. Oder du musst mit PyPy und sehr speziellen Datenstrukturen arbeiten, die du dir selbst erarbeitest. Das ist hochperformance-Programmierung. Netter Talk dazu: https://www.youtube.com/watch?v=NH1Tta7purM

Das liefert dir hier keiner mal so zwischen Tuer und Angel. Wenn ich sowas machen soll, dann prognostiziere ich tagelange Arbeit, und 5-Stellige Betraege auf meinem Konto. Das ist kein Scherz. Da ist man ein paar Wochen mit beschaeftigt.

[kbr]

Je nach Datenstruktur nutzt Du womöglich den falschen Algorithmus.

Sequenzen in einer Liste kannst Du direkt mit .sort() oder sorted() sortieren. Per default wird für die Sortierreihenfolge das erste Element jeder Sequenz betrachtet. Die Sortierung erfolgt zudem für Python ziemlich schnell. Wenn Du keine Funktion an key übergibst (was in Deinem Fall nicht erforderlich ist), wird der Sortiervorgang noch einmal um knapp 50% beschleunigt.

Kann ein Preis pro Orderbook nur einmal vorkommen, bietet sich ein Dictionary an. Lookup erfolgt hier in annähernd in O(1). Brauchst Du die keys in sortierter Reihenfolge, so kannst Du diese separat sortieren.

Prinzipiell ist es für Deine Anwendung von Vorteil, wenn Du weißt, an welchem Index (oder Hashwert) ein entsprechender Eintrag zu finden ist. Dementsprechend solltest Du die Datenstruktur des Orderbooks entwerfen.

Vielleicht brauchst Du auch eine als shared object kompilierte Extension. Aber auch da brauchst Du den richtigen Algorithmus, sonst ist auch das womöglich zu langsam. Ja nach Details, die sich dann auftun, kann __deets__ Kostenabschätzung sehr reell sein.

[Sirius3]

Den Code, den Du gezeigt hast, ließe sich noch verbessern, indem man die vielen Dereferenzierungen verringert, Eine Variable sollte keine zwei Typen haben (List und Bool), None wäre besser als False und noch besser wäre es einen else-Block zu benutzen.

Code: Alles auswählen

bids = self._orderbook[symbol]["bids"]
try:
    item = bids.find(preis)
except ValueError: # dann gibts den eintrag noch nicht
    if menge != 0:
        bids.insert([preis, menge])
else:
    if menge != 0:
        item[2] = menge
    else: # ist 0, dann entfernen
        bids.remove(item)

Exceptions sind langsam, tritt der Fall oft auf, ist es eventuell schneller, index zu benutzen.
Nun sind Listen updaten langsame Operationen, weil der komplette Inhalt kopiert werden muß. Da wie schon geschrieben, die meisten Operationen davon schon in C implementiert sind, kann man mit dieser Struktur auch keine Geschwindigkeitswunder erwarten.
Statt dessen sind Bäume die Struktur, die man üblicherweise für solche Aufgaben einsetzt. Davon gibt es wiederum etliche Varianten, welche für Deinen Anwendungsfall die beste ist, mußt Du selbst herausfinden. Bei vielen Updates kann es von Nutzen sein, keinen vollständig balancierten Baum zu benutzen.

Wie schon geschrieben, bevor man anfängt, ohne Verstand zu Optimieren, geht es darum, einen passenden Algorithmus zu finden. Erster Schritt ist es, zu ermitteln, wieviele Inserts, Removes und Updates es gibt, wobei bei Dir im Moment Updates O(log(n)) haben, Inserts und Removes dagegen O(n).

[Scholastik]

Vielen Dank.

Ich würde gerne pypy unter windows ausprobieren, habe von der websicte die python 3.5 version runtergeladen, als zip datei. Beim entpacken fällt mir jetzt auf, dass das scheinbar nichts zum installieren ist,wenn ich die pypy3.exe starte, wird direkt ein interpreter gestartet.
Soweit erstmal nicht so schlimm, da ich es fürs ausprobieren ohnehin nicht fest installieren wollen würde, falls es nicht hilft. Allerdings bin ich jetzt überfragt, wie ich mein Skript nun mit pypy ausführen kann? Ich bins gewohnt in der kommandozeile/ windows powershell einfach python meinskript.py einzutippüen und fertig, aber das wird ohne echte pypy installation ja sicher nicht funktionieren.
Also wo muss ich mein Skript nun in dem pypy Ordner hinschieben und wie starte ich es mit pypy?

Ansonsten:
Ich habe mal einige live updates mitgeschnitten und ein testskript geschrieben, welches eben nur die Verarbeitung dieser updates enthält. Es sind 1 Million updates und mein PC windows arbeitet sie im testskript innerhalb von 3.5 sekunden ab und mein debian 8.1 server, wo das ganze letzlich laufen soll (und angeblich zu langsam ist) schafft das in ca. 6 sekunden, was also ~120.000 updates pro sekunde entspricht und damit eigentlich 10mal schneller als die 400updates alle 35ms brauchen sollten. Vermutlich muss ich jetzt noch ein wenig tiefer testen, wo und warum es im nicht-test-betrieb dennoch zu verzögerungen kommt...

Ein dictionary war übrigens meine vorherige Struktur, bevor ich bisect kannte. Das ist tatsächlich schön schnell beim updaten, aber je nach dem wie oft man dann eine tatsächlich sortierte Version benötigt, ist es dann doch wieder zu langsam. Also das updaten geht superschnell, aber das sortierte abrufen dauert lange. bisect (=sortedcollection) ist da schon das schnellste was ich bisher gefunden habe. Und zum Thema "Bäume/trees" davon habe ich absolut keine Ahnung, bin aber auf diese Begriffe bei meiner Recherche gestoßen und häufig wurde geschrieben, dass bisect bzw sortedContatiners schneller als trees wäre, weshalb ich das nicht weiter verfolgt habe.

edit zu pypy:
Habe die skripte nun einfach indenselben ordner wie die pypy3.exe getan und mit der powershell in den ordner navgiert und .\pypy3 meinskript.py eingetippt.
Das einlesen der 1Million updates aus einer txt Datei hat doppelt so lange wie mit python gedauert, ABER das durchgehen der updates ist tatsächlich 2-3 mal so schnell ! Wow, damit hätte ich nicht gerechnet.
Jetzt fangen die schwierigen Dinge aber vermutlich erst an, oder? Für PyPy müsste ich ja vermutlich alle Module wie requests usw die ich für python verwende, auch für Pypy installieren und sicherlich gibt es da wieder diverse Kompatibilitätsprobleme und auch das installieren auf Linux (debian) soll wohl nicht so einfach sein, wobei auf der website geraten wird pypy direkt von debian zu beziehen...
->
Es gibt nicht zufällig eine Möglichkeit, wie ich alles wie gewohnt in python laufen lassen kann, aber diese updates in pypy auslagere und dennoch alles zusammenlaufen kann, sodass die python skripte zugriff auf die pypy infos haben?
edit2: werde mir mal numba angucken, welches ja ebenfalls JIT hat und scheinbar mit normalem python kombiniert werden kann. mal gucken wieviel schneller es dadurch wird.

[__deets__]

Man kann mittels Interprozesskommunikation irgendwas basteln, um Python und pypy kollabieren zu lassen. Ob das nun aber die geringere Herausforderung darstellt und dazu auch noch Performant genug bleibt - weiß keiner.

Für pure Python Pakete sollte pypy aber gut funktionieren. Die Zeit auszuprobieren es nur damit zu machen solltest du dir nehmen.

[Scholastik]

Man kann mittels Interprozesskommunikation irgendwas basteln, um Python und pypy kollabieren zu lassen. Ob das nun aber die geringere Herausforderung darstellt und dazu auch noch Performant genug bleibt - weiß keiner.

Für pure Python Pakete sollte pypy aber gut funktionieren. Die Zeit auszuprobieren es nur damit zu machen solltest du dir nehmen.

ne, ausschließlich mit pypy arbeiten ist leider keine Option. Ich verwende soviele Module und hab schon probleme nur python selbst zu installieren, weshalb pypy nach wochenlangem Frust in einem absolutem Disaster enden würde. Zumal ja auch nicht alles beschleunigt wird, das auslesen aus der txt Datei dauert ja doppelt so lange. Also scheint es auch nicht sinnvoll pypy für alles zu nutzen.

Ich experimentiere gerade mit numba, aber das scheint ja auch wirklich ne kleine Herausforderung zu sein. Es gibt soviele Fälle in denen es irgendwelche abstrusen Fehlermeldungen auswirft, ganz besonders wenn man der Fkt zb eine Liste übergeben will, die weiter gefüllt werden soll. In unserm Fall will ich ja dass mit dem orderbook, also einer Liste, weiter gearbeitet wird. Aber innerhalb einer Klasse scheint numba nicht zu funktionieren und außerhalb einer Klasse müsste ich ihm ja das orderbook übergeben, damit es daran bastelt, doch das funktioniert zumindest dann nicht, wenn die liste noch leer ist.... mal weiter basteln...

[Scholastik]

hm, ne, numba scheint nicht anwendbar zu sein, oder?

Habe jetzt rausgefunden ,dass nicht nur leere listen probleme bereiten, sondern auch verschachtelte Listen. also [3,4] zu übergeben, funktioniert, aber [[3,4],...] funktioniert schon nicht mehr. Und da ein orderbook nunmal so aussieht, bzw sortedcollection vermutlich ähnlich aussieht, sehe ich keinen Weg, wie ich in einer mit numba (njit) decorierten Funktion die udpates in das orderbook einpflegen kann... oder was übersehe ich?

[noisefloor]

Hallo,

also ich hatte mit Numba keine Problem. Funktionen dekorieren, laufen lassen, fertig. Numba war bei meinen Tests (stunpfes Testen auf Primzahlen) auch schneller als PyPy.

Ansonsten müsstest du den relevanten Codeteil und die _genaue_ Fehlermeldung von Python + Numba mal zeigen.

Gruß, noisefloor

[Sirius3]

@Scholastik: darf ich es nocheinmal wiederholen: alle relevanten Teile Deines Beispielcodes sind schon in C implementiert. Geschwindigkeitswunder wirst Du nicht erwarten können. Der Algorithmus, den Du gerade verwendest, ist halt nicht geeignet.

[sparrow]

@Scholastik:

Warum brauchst du die Daten denn überhaupt sortiert?
Denn du schreibst weiter oben, dass ein dict (was sich ja für diese Art der Datenhaltung regelrecht aufdrängt und mit Signalfackel auf sich aufmerksam machen will) in den Zugriffen ausgesprochen schnell ist, nur die Sortierung dauert.
Daher die Frage, warum sortieren, wenn das zeitkritische Element das Zeitnahe aufnehmen von Daten in die Datenstruktur ist. Für eine Visualisierung ist das Sortieren zum Beispiel nicht zeitkritisch.

Vom grünen Tisch wirkt das so, als würdest du den zweiten Schritt vor dem ersten tun. Du nimmst externe Tools, die hochoptimieten Code optimieren sollen, übersiehst dabei aber, dass dein Code nicht (für das gegebene Problem) optimiert ist.

[Scholastik]

@Sirius:
du darfst dich wiederholen, aber den Sinn dahinter versteh ich nicht Mein Algorithmus, also bisect zu verwenden ist schon super (du darfst mir aber gerne sagen was genau noch besser ist und nicht nur allgemein dass irgendwelche "bäume" besser sein könnten, denn ich habe wie gesagt schon die gegenteilige Meinung gelesen -> es steht Behauptung gegen Behauptung) und dass cython nicht mehr viel hilft hatte ich ja auch oben schon selbst gemerkt. Pypy hingegen hat tatsächlich geholfen, weshalb ich mir nun mit numba ein ähnliches ergebnis erhofft habe, ohne dass ich gleich alles umstellen muss.

Hallo,
also ich hatte mit Numba keine Problem. Funktionen dekorieren, laufen lassen, fertig. Numba war bei meinen Tests (stunpfes Testen auf Primzahlen) auch schneller als PyPy.
Ansonsten müsstest du den relevanten Codeteil und die _genaue_ Fehlermeldung von Python + Numba mal zeigen.

Gruß, noisefloor

Sagen dir meine genannten Einschränkungen denn nichts (also sollte es diese nicht geben?)? Neben verschachtelten Listen kann man scheinbar auch keine eigenen Funktionen in der dekorierten Funktion aufrufen (zumindest bei njit, mit jit hab ichs noch nicht probiert). Du kennst ja sortedCollection und du kennst meinen Code der die updates einpflegt. Wie/an welcher stelle würdest du da eine mit @jit oder @njit dekorierte Funktion ansetzen?

@sparrow:
na der Sinn davon real time orderbook daten zu haben, ist auch real time zu traden. Dh. ich muss mithilfe der orderbookdaten diverse Berechnungen durchführen, und das möglichst oft um innerhalb weniger milisekunden reagieren zu können. Im aktuellen Aufbau mache ich diese Berechnungen alle 0.1 sekunden, brauche also ein sortiertes orderbook alle 0.1 sekunden. Ich habe mir bereits Gedanken darüber gemacht, ob es sinnvoll wäre, das ganze nicht linear, sondern zb auf eventbassis oder ähnliches zu programmieren, aber das macht für meine trading strategie keinen Sinn. Denn 1) Wie will man bei zig updates alle 35ms irgendeine Berechnung auf Basis eines events anstoßen (das wären dann ja noch deutlich häufigere Berechnungen als alle 0.1 sekunden)? Und 2) darf die nächste Rechnung ohnehin erst angestoßen werden, wenn die vorherige fertig ist, bzw je nach Ergebnis der Berechnung, darauf reagiert wurde. Und ich glaube es gibt nur diese 2 Möglichkeiten, oder? (also entweder alle x sekunden berechnen und alles nacheinander machen, oder stattdessen auf ein event von außen warten und darauf dann reagieren)

[Sirius3]

@Scholastik: ich habe Dir exakt geschrieben, dass das Einfügen von Elementen in eine Liste eine O(n)-Operation ist, die langsam ist, die bei Bäumen, je nach Ausführung eine O(1) oder eine O(log(n))-Operation ist. Wo hast Du die gegenteilige Meinung gelesen, bitte Referenz.
Ich bin hier auch nicht da, Dir den fertigen Algorithmus zu liefern, sondern sage Dir nur, welcher besser ist, nicht im Konjunktiv, sondern mathematisch bewiesen.
Was Du sonst noch an Code hast, wo PyPy etwas hilft, weiß hier ja keiner.

[Scholastik]

@Scholastik: ich habe Dir exakt geschrieben, dass das Einfügen von Elementen in eine Liste eine O(n)-Operation ist, die langsam ist, die bei Bäumen, je nach Ausführung eine O(1) oder eine O(log(n))-Operation ist. Wo hast Du die gegenteilige Meinung gelesen, bitte Referenz.
Ich bin hier auch nicht da, Dir den fertigen Algorithmus zu liefern, sondern sage Dir nur, welcher besser ist, nicht im Konjunktiv, sondern mathematisch bewiesen.
Was Du sonst noch an Code hast, wo PyPy etwas hilft, weiß hier ja keiner.

danke, habe jetzt mal nach den stichworten tree und real time orderbook gesucht und bin auf das hier gestoßen, welches wohl trees und C verwendet und bzgl O() schneller sein soll:
https://github.com/Crypto-toolbox/HFT-Orderbook
ich werd mal gucken, ob ich damit was zum laufen bekomme um es zu testen.

Pypy hat sowohl meinen Code im Eingangspost beschleunigt, als auch den testcode welcher 1 million updates durchspielt, bei dem wirklich nicht viel mehr code ist, als euch bekannt ist. Interessant find ich, dass der Code im Eingangspost mit pypy so wie er da steht tatsächlich langsamer ist, aber wenn man die "testliste" neu zusammenstellt, also zb "for i in range(1000): testliste.append([i,2])", dann ist pypy sogar 10 mal schneller als python. Aber naja, da ich pypy ohnehin nicht verwenden werde, ist das auch egal.