Сообщение Отрезки и точки. Считать вхождение. от 17.02.2021 14:12
Изменено 17.02.2021 15:30 Sharov
Отрезки и точки. Считать вхождение.
Здравствуйте.
Сильно в фоновом режиме прохожу курс института Сан-Диего по алгоритмам.
Так сказать, гешефт прикрываю
И конкретно туплю на простой и базовой задаче про подсчет вхождения точек в отрезки. У меня временной интервал
(не знаю единиц) что-то типа 500 из 20. где туплю, но туплю, видимо, сильно. В общем вот:
Глава называется Divide and Conquer, ничего лучше чем отсортировать, бинарным поиском отсечь лишнее, а дальше
по всем оставшимся пройти и проверить, я не придумал. Однако в одном из тестов по времени я сильно не укладываюсь,
причем сами данные не показывают....
ЧЯДНТ? Думается, что можно как-то избавиться от циклов после (дважды)бинарного поиска...
Сильно в фоновом режиме прохожу курс института Сан-Диего по алгоритмам.
Так сказать, гешефт прикрываю
И конкретно туплю на простой и базовой задаче про подсчет вхождения точек в отрезки. У меня временной интервал
(не знаю единиц) что-то типа 500 из 20. где туплю, но туплю, видимо, сильно. В общем вот:
#скачал из интернетов -- возвращает число меньших эл-во чем заданный в отсортированном массиве
def binarySearchCount(arr: List[Tuple[int, int]],item, key):
left = 0
n = len(arr)
right = n - 1
count = 0
while left <= right:
mid = (right + left) // 2
# Check if middle element is
# less than or equal to key
if arr[mid][item] < key:
# At least (mid ) elements are there
# whose values are less than
# or equal to key
count = mid
left = mid + 1
# If key is smaller, ignore right half
else:
right = mid - 1
return count
def fast_count_segments(starts: List[int], ends: List[int], points: List[int]):
cnt = [0] * len(points)
tups_sort_by_end = [(starts[i], ends[i]) for i in range(len(ends))]
tups_sort_by_start = [(starts[i], ends[i]) for i in range(len(ends))]
# сортирую по началу и концу nlog(n)
tups_sort_by_end.sort(key=lambda tup: tup[1])
tups_sort_by_start.sort(key=lambda tup: tup[0])
l_s = len(tups_sort_by_end)
d = {}
for i in range(len(points)):
if points[i] in d:
cnt[i] = d[points[i]]
continue
# смотрю, где меньше итераций(к началу или к концу)
idx_e = binarySearchCount(tups_sort_by_end, 1, points[i])
idx_s = binarySearchCount(tups_sort_by_start, 0, points[i])
# лежит во всех интервалах, готово, идем дальше
if idx_s == l_s and idx_e == 0:
cnt[i] = l_s
else:
if idx_s == idx_e:
for j in range(idx_e, l_s):
if tups_sort_by_end[j][0] <= points[i] <= tups_sort_by_end[j][1]:
cnt[i] += 1
else:
if idx_s > l_s - idx_e:
# к концу быстрее
for j in range(idx_e, l_s):
if tups_sort_by_end[j][0] <= points[i] <= tups_sort_by_end[j][1]:
cnt[i] += 1
else:
# к началу быстрее
for j in range(0, idx_s + 1):
if tups_sort_by_start[j][0] <= points[i] <= tups_sort_by_start[j][1]:
cnt[i] += 1
d[points[i]] = cnt[i]
return cnt
Глава называется Divide and Conquer, ничего лучше чем отсортировать, бинарным поиском отсечь лишнее, а дальше
по всем оставшимся пройти и проверить, я не придумал. Однако в одном из тестов по времени я сильно не укладываюсь,
причем сами данные не показывают....
ЧЯДНТ? Думается, что можно как-то избавиться от циклов после (дважды)бинарного поиска...
Отрезки и точки. Считать вхождение.
Здравствуйте.
Сильно в фоновом режиме прохожу курс института Сан-Диего по алгоритмам.
Так сказать гешефт прикрываю
И конкретно туплю на простой и базовой задаче про подсчет вхождения точек в отрезки. У меня временной интервал
(не знаю единиц) что-то типа 500 из 20. где туплю, но туплю, видимо, сильно. В общем вот:
Глава называется Divide and Conquer, ничего лучше чем отсортировать, бинарным поиском отсечь лишнее, а дальше
по всем оставшимся пройти и проверить, я не придумал. Однако в одном из тестов по времени я сильно не укладываюсь,
причем сами данные не показывают....
ЧЯДНТ? Думается, что можно как-то избавиться от циклов после (дважды)бинарного поиска...
Сильно в фоновом режиме прохожу курс института Сан-Диего по алгоритмам.
Так сказать гешефт прикрываю
И конкретно туплю на простой и базовой задаче про подсчет вхождения точек в отрезки. У меня временной интервал
(не знаю единиц) что-то типа 500 из 20. где туплю, но туплю, видимо, сильно. В общем вот:
#скачал из интернетов -- возвращает число меньших эл-во чем заданный в отсортированном массиве
def binarySearchCount(arr: List[Tuple[int, int]],item, key):
left = 0
n = len(arr)
right = n - 1
count = 0
while left <= right:
mid = (right + left) // 2
# Check if middle element is
# less than or equal to key
if arr[mid][item] < key:
# At least (mid ) elements are there
# whose values are less than
# or equal to key
count = mid
left = mid + 1
# If key is smaller, ignore right half
else:
right = mid - 1
return count
def fast_count_segments(starts: List[int], ends: List[int], points: List[int]):
cnt = [0] * len(points)
tups_sort_by_end = [(starts[i], ends[i]) for i in range(len(ends))]
tups_sort_by_start = [(starts[i], ends[i]) for i in range(len(ends))]
# сортирую по началу и концу nlog(n)
tups_sort_by_end.sort(key=lambda tup: tup[1])
tups_sort_by_start.sort(key=lambda tup: tup[0])
l_s = len(tups_sort_by_end)
d = {}
for i in range(len(points)):
if points[i] in d:
cnt[i] = d[points[i]]
continue
# смотрю, где меньше итераций(к началу или к концу)
idx_e = binarySearchCount(tups_sort_by_end, 1, points[i])
idx_s = binarySearchCount(tups_sort_by_start, 0, points[i])
# лежит во всех интервалах, готово, идем дальше
if idx_s == l_s and idx_e == 0:
cnt[i] = l_s
else:
if idx_s == idx_e:
for j in range(idx_e, l_s):
if tups_sort_by_end[j][0] <= points[i] <= tups_sort_by_end[j][1]:
cnt[i] += 1
else:
if idx_s > l_s - idx_e:
# к концу быстрее
for j in range(idx_e, l_s):
if tups_sort_by_end[j][0] <= points[i] <= tups_sort_by_end[j][1]:
cnt[i] += 1
else:
# к началу быстрее
for j in range(0, idx_s + 1):
if tups_sort_by_start[j][0] <= points[i] <= tups_sort_by_start[j][1]:
cnt[i] += 1
d[points[i]] = cnt[i]
return cnt
Глава называется Divide and Conquer, ничего лучше чем отсортировать, бинарным поиском отсечь лишнее, а дальше
по всем оставшимся пройти и проверить, я не придумал. Однако в одном из тестов по времени я сильно не укладываюсь,
причем сами данные не показывают....
ЧЯДНТ? Думается, что можно как-то избавиться от циклов после (дважды)бинарного поиска...