{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# 🔥binary search vs glob.glob🔥\n+ TL;DR\n  + I've compared the performance on finding first/last dcms in each directory\n  + The performance of binary search seems to be unstable\n  + In many runs, glob.glob was about 1.2x~ faster than binary search\n    + 4.2〜4.4s (glob.glob) vs 5.2〜5.6s (binary search)\n    + (After I've published this notebook, I noticed that \"Run All\" may not remove cache and the above result isn't applicable to cold cache runs)","metadata":{}},{"cell_type":"code","source":"import glob\nimport os\nimport pandas as pd\nimport time","metadata":{"execution":{"iopub.status.busy":"2022-10-14T14:01:20.593167Z","iopub.execute_input":"2022-10-14T14:01:20.593608Z","iopub.status.idle":"2022-10-14T14:01:20.599644Z","shell.execute_reply.started":"2022-10-14T14:01:20.593574Z","shell.execute_reply":"2022-10-14T14:01:20.598185Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"train_df = pd.read_csv('../input/rsna-2022-cervical-spine-fracture-detection/train.csv')\ntrain_df","metadata":{"execution":{"iopub.status.busy":"2022-10-14T14:01:20.603643Z","iopub.execute_input":"2022-10-14T14:01:20.604386Z","iopub.status.idle":"2022-10-14T14:01:20.634749Z","shell.execute_reply.started":"2022-10-14T14:01:20.604311Z","shell.execute_reply":"2022-10-14T14:01:20.633365Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"uniq_uids = pd.unique(train_df.StudyInstanceUID)\n\nt1 = time.time()\nfirst_last_list1 = []\nfor uid in uniq_uids:\n    files = glob.glob(f'../input/rsna-2022-cervical-spine-fracture-detection/train_images/{uid}/*.dcm')\n    dcms = sorted(map(lambda item: int(item.split(\"/\")[-1].replace('.dcm', '')), files))\n    first_last_list1.append((dcms[0], dcms[-1]))\nt2 = time.time()\nprint(\"time: \", t2 - t1)","metadata":{"execution":{"iopub.status.busy":"2022-10-14T14:01:20.636723Z","iopub.execute_input":"2022-10-14T14:01:20.637138Z","iopub.status.idle":"2022-10-14T14:01:25.090712Z","shell.execute_reply.started":"2022-10-14T14:01:20.637101Z","shell.execute_reply":"2022-10-14T14:01:25.0894Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"def binary_search(lower_bound, upper_bound, uid):\n    for _ in range(12):\n        med = lower_bound + int((upper_bound - lower_bound) / 2.0)\n        if os.path.exists(f'../input/rsna-2022-cervical-spine-fracture-detection/train_images/{uid}/{med}.dcm'):\n            lower_bound = med\n        else:\n            upper_bound = med\n    return upper_bound - 1\n\ndef find_min_index(uid):\n    if os.path.exists(f'../input/rsna-2022-cervical-spine-fracture-detection/train_images/{uid}/1.dcm'):\n        return 1\n    if uid == '1.2.826.0.1.3680043.17166':\n        return 59\n    return 2\n\nt1 = time.time()\nfirst_last_list2 = []\nfor uid in uniq_uids:\n    first_last_list2.append((find_min_index(uid), binary_search(1, 2500, uid)))\nt2 = time.time()\nprint(\"time: \", t2 - t1)","metadata":{"execution":{"iopub.status.busy":"2022-10-14T14:01:25.092811Z","iopub.execute_input":"2022-10-14T14:01:25.093351Z","iopub.status.idle":"2022-10-14T14:01:31.105923Z","shell.execute_reply.started":"2022-10-14T14:01:25.093316Z","shell.execute_reply":"2022-10-14T14:01:31.104554Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"first_last_list1 == first_last_list2","metadata":{"execution":{"iopub.status.busy":"2022-10-14T14:01:31.108035Z","iopub.execute_input":"2022-10-14T14:01:31.108386Z","iopub.status.idle":"2022-10-14T14:01:31.11517Z","shell.execute_reply.started":"2022-10-14T14:01:31.108355Z","shell.execute_reply":"2022-10-14T14:01:31.114255Z"},"trusted":true},"execution_count":null,"outputs":[]}]}