Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
55 / 55 / 16
Регистрация: 25.03.2013
Сообщений: 178

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

13.02.2014, 01:26. Показов 1826. Ответов 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): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru