55 / 55 / 16
Регистрация: 25.03.2013
Сообщений: 178

Как сделать эффективнее код подсчета длины отрезков (использование регулярных выражений, сортировки)

13.02.2014, 01:26. Показов 1834. Ответов 5
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Файл in.txt cодержит корректные вещественные координаты отрезков на плоскости (по одному отрезку в строке) в формате:
(x1;y1) (x2;y2)
1) Создать список вида (len; num) где len – длинна отрезка, округлённая до целого значения, а num – количество отрезков длины len.
2)*Отсортировать список по убыванию num.
Пример

Пример файла in.txt:
(0 ; 0) ( 2,5; 0)
( 0;1) ( 0; 2 )
(-3,0; 20,1e-1) (-2;2)
Вывод:
1;2
3;1

Примечания к задаче

– Строку разобрать методом split(*) через регулярное выражение. Формат строки (неформально):
\s*(\s*вещ.число\s*;\s*вещ.число\s*)\s*( \s*вещ.число\s*;\s*вещ.число\s*)\s*
Вещественное число во входной строке правильное. Пары скобок и точка с запятой между числами гарантированно имеются. Учитывать данные условия при составлении регулярного выражения. Не нужно подбирать выражение под вещественное число. Оно далеко не тривиальное.
– Цикл с линейным поиском элемента запрещается, т.к. очень неэффективный.
– Длина отрезка = sqrt((x1– x2)2 + (y1–y2)2) – это на всякий случай;
– чтобы половинные значения округлялись к большему, нужно вызывать Round;
– Очевидное решение основано на классе list. У кого будет запас времени, поищите более изящное решение.

Мой код
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# -*- coding: utf-8 -*-
# using python 2.7.3
 
import re
 
#pattern for search coordinates of float numbers
coordinats_pattern = re.compile(r'[(]\s*([-]?\d+(?:\,\d+)?(?:[eE][+-]\d+)?)\s*'
    r';\s*([-]?\d+(?:\,\d+)?(?:[eE][+-]\d+)?)\s*[)]\s*'
r'[(]\s*([-]?\d+(?:\,\d+)?(?:[eE][+-]\d+)?)\s*;'
    r'\s*([-]?\d+(?:\,\d+)?(?:[eE][+-]\d+)?)\s*[)]')
with open('in.txt','rb') as f:
    lines = f.read()
    iterator = coordinats_pattern.finditer(lines) 
    #generates list of length segments
    list_len = [round(((float(match.group(1).replace(',','.'))-\
        float(match.group(3).replace(',','.')))**2+\
    (float(match.group(2).replace(',','.'))-\
        float(match.group(4).replace(',','.')))**2)**0.5,0) for match in iterator]
    #generates list of tuples = (len;num)
    out = [(i,list_len.count(i)) for i in list_len]
    #sorting
    out.sort(key=lambda x:x[1],reverse=True)
    #transform list in set for removing of repeats
    for tup in set(out):
        print '{0:.0f};{1}'.format(tup[0],tup[1])

Вопрос в том насколько код рационален(может лучше не использовать рег экспы, не считать для всех длин их количество, т.к. лишние вычисления и соответственно не нужно во множество переводить) и соответствует примечаниям к задаче.
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
13.02.2014, 01:26
Ответы с готовыми решениями:

Использование регулярных выражений
Добрый День! Имеется строка в виде <Symbol>GRX/SPB</Symbol> <ContractPosition>-100</ContractPosition>...

Использование регулярных выражений
Доброго времени суток, уважаемые форумчане! Подскажите пожалуйста. Уже мозг сломал. Есть массив $arrayA, содержащий множество...

Использование регулярных выражений
Определите три наиболее популярных вида спорта в стране, исходя из количества построенных спортивных объектов для них. Файл с данными...

5
224 / 209 / 63
Регистрация: 26.05.2011
Сообщений: 363
13.02.2014, 06:46
Лучший ответ Сообщение было отмечено Zarex как решение

Решение

Строка 22 в Вашем коде лишняя, потому что set не сохраняет порядок следования элементов.
Предлагаю следующий вариант:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/python3.3
# -*- mode: python; coding: utf-8 -*-
 
import re
from collections import Counter, defaultdict
from operator import itemgetter
 
def calculate(in_file_name):
    """"""
 
    SEGMENT = re.compile(r"\s*\(\s*(\S*?)\s*;\s*(\S*?)\s*\)" * 2)
    result = Counter()
 
    with open(in_file_name, "rt", encoding="utf-8") as f:
        for line in f:
            seg = tuple(map(float,
                    (_.replace(",", ".") for _ in SEGMENT.findall(line)[0])))
            seg_len = ((seg[0] - seg[2]) ** 2 + (seg[1] - seg[3]) ** 2) ** .5
 
            result[round(seg_len + .45)] += 1
 
    return result.most_common()
 
 
def calculate2(in_file_name):
    """"""
 
    SEGMENT = re.compile(r"\s*\(\s*(\S*?)\s*;\s*(\S*?)\s*\)" * 2)
    result = defaultdict(int)
 
    with open(in_file_name, "rt", encoding="utf-8") as f:
        for line in f:
            seg = tuple(map(float,
                    (_.replace(",", ".") for _ in SEGMENT.findall(line)[0])))
            seg_len = ((seg[0] - seg[2]) ** 2 + (seg[1] - seg[3]) ** 2) ** .5
            result[round(seg_len + .45)] += 1
 
    return sorted(result.items(), key=itemgetter(1), reverse=True)
 
 
def calculate3(in_file_name):
    """"""
 
    SEGMENT = re.compile(r"\s*\(\s*(\S*?)\s*;\s*(\S*?)\s*\)" * 2)
    result = {}
 
    with open(in_file_name, "rt", encoding="utf-8") as f:
        for line in f:
            seg = tuple(map(float,
                    (_.replace(",", ".") for _ in SEGMENT.findall(line)[0])))
            seg_len = ((seg[0] - seg[2]) ** 2 + (seg[1] - seg[3]) ** 2) ** .5
            seg_len = round(seg_len + .45)
            result[seg_len] = result.get(seg_len, 0) + 1
 
    return sorted(result.items(), key=itemgetter(1), reverse=True)
1
55 / 55 / 16
Регистрация: 25.03.2013
Сообщений: 178
13.02.2014, 13:50  [ТС]
pyuser, спасибо большое за целых три варианта. я сам догадывался что мой код отстой, но всё-же почему-то думал что множества сохраняют порядок элементов.
p.s. буду учиться тестить на скорость выполнения скрипты

Добавлено через 57 минут

Не по теме:

может есть возможность замера времени работы скрипта путем использования timeit в консоли windows 7 при запуске оного скрипта. Типа такого:

Python
1
...\python\task>python <название_скрипта.py> timeit -c
извините за оффтоп

0
 Аватар для Wolkodav
842 / 480 / 58
Регистрация: 18.09.2012
Сообщений: 1,688
14.02.2014, 00:01
Типо такого:
Python
1
2
3
4
5
6
7
8
9
import time
def howlong(f):
   def tmp(*args, **kwargs):
       t = time.time()
       res = f(*args, **kwargs)
       print "time: %f" % (time.time()-t)
       return res
 
   return tmp
осталось перед функцией написать @howlong и готово)
Проще:
Python
1
2
3
4
5
6
import time
start = time.time()
main() # Ну тут вызов вашей функции, жалетельно без raw_input
# Что бы не тратить время на ввод данных, а сразу туда их передавать
finish = time.time()
print (finish - start)
P.S. Декоратор так, побаловаться)
1
224 / 209 / 63
Регистрация: 26.05.2011
Сообщений: 363
14.02.2014, 03:11
Цитата Сообщение от Zarex Посмотреть сообщение
за целых три варианта
Вариант один, просто контейнеры для накопления результатов разные.
Цитата Сообщение от Wolkodav Посмотреть сообщение
Декоратор так, побаловаться
Ну если только побаловаться, то вот еще вариант:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import gc
import timeit
 
class Timer(object):
    def __init__(self, timer=None, disable_gc=False, verbose=True):
        if timer is None:
            timer = timeit.default_timer
        self.timer = timer
        self.disable_gc = disable_gc
        self.verbose = verbose
        self.start = self.end = self.interval = None
 
    def __enter__(self):
        if self.disable_gc:
            self.gc_state = gc.isenabled()
            gc.disable()
        self.start = self.timer()
        return self
 
    def __exit__(self, exc_type, exc_value, traceback):
        self.end = self.timer()
        if self.disable_gc and self.gc_state:
            gc.enable()
        self.interval = self.end - self.start
        if self.verbose:
            print('time taken: {} seconds'.format(self.interval))
 
 
with Timer():
    # блок кода, тестируемый на скорость выполнения
1
55 / 55 / 16
Регистрация: 25.03.2013
Сообщений: 178
14.02.2014, 11:57  [ТС]
Wolkodav, pyuser, спасибо большое. Но это я так понимаю это "изнутри" скрипта, а я имел ввиду нечто другое: можно ли передавать текст исполняемого скрипта в консоли timeit как многострочный текст. Типа такого:
Bash
1
2
C:\>python -m timeit """ 5 ** 5 / 10**1000000 """
100000000 loops, best of 3: 0.0171 usec per loop
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
14.02.2014, 11:57
Помогаю со студенческими работами здесь

Использование регулярных выражений
Перемещено из Поиск в массиве топик-стартер наверно имел ввиду поиск строки в текстовом файле. как один из вариантов это поиск...

Использование регулярных выражений
Здравствуйте. Подскажите, пожалуйста, как будет выглядеть такая ссылка в виде регулярного выражения: &lt;br /&gt; и если таких ссылок,...

Использование регулярных выражений
Доброе утро, подскажите пожалуйста, совсем запуталась. У меня есть модуль, нужно, чтобы внутри процедуры Заполнить выполнялись процедуры...

Использование регулярных выражений
На входе есть некая последовательность символов А, представленная в виде массива. Нужно, используя регулярное выражение, найти...

Использование регулярных выражений
Вот задание - Дан текст и слово, вывести все слова из текста не абсолютно совпадающие с введенным словом. Вот всё что я сделал, вроде...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

Новые блоги и статьи
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru