DjangoBB LoFi version

1 2

dingo

Апрель 16, 2012 10:19:26

Во входном файле дана серия из M последовательностей. При этом гарантированно что каждое число ,кроме одного встречается четное кол-во раз. Нужно найти число, которое встречается нечетное кол-во раз
Формат входного файла
Каждая последовательность начинается с числа Nj , которая показывает сколько чисел в j-ой последовательности.
Затем перечислены все числа входящие в эту последовательность разделенные пробелами или символом перевода строки. В конце входного файла записан 0.
Формат выходного файла
Требуется вывести M чисел , каждое из которых будет именно тем числом которое встречается нечетное кол-во раз в j-ой последовательности.
Есть программа , но она медленная.
Как ее можно ускорить?

def proverka(spisok):
	id=[]
	dlina=len(spisok)
	for q in spisok:
		if q not in id:
			id.append(q)
	for q in id:
		if spisok.count(q)%2!=0:
			return q
f=open("xorr.in")
l=f.read()
f.close()
s=l.split()
dlina=len(s)-1
i=0
spisok=[]
otvet=""
while i!=dlina:
	start=int(s[i])
	temp=[]
	i+=1
	while start!=0:
		 temp.append(int(s[i]))
		 i+=1
		 start-=1
	spisok.append(temp)
for q in spisok:
	otvet=otvet+str(proverka(q))+"\n"
f=open("xorr.out","w")
f.write(otvet)
f.close()

ilnur

Апрель 16, 2012 11:53:33

ух. покажи структуру одну последовательности. цифрами. и опиши. так ничего я не понял
:|

fata1ex

Апрель 16, 2012 12:49:16

1. В функции proverka используйте словарь. Вы выполняете двойную работу, сначала создавая список, а потом проходя его еще раз для каждого элемента. d = { number : count , … }.
2. Используйте comprehension'ы, когда это возможно
3. Для работы с файлами используйте контекстные менеджеры. Незачем читать сразу весь файл, читайте его построчно.
4. Манипуляции в циклах ужасны. Зачем сначала создавать список, а потом его обрабатывать? Зачем вам вообще отдельная функция для этого? Заведите словарь и для каждой последовательности заполняйте его, потом находите нужный элемент, а словарь очищаете.
5, 6,7,8,9,… Называйте переменные и функции по-человечески. Приучайтесь к хорошему коду.

ilnur, прочитай повнимательнее :)

dingo

Апрель 16, 2012 22:55:46

После небольшой переработки вот что получилось

f=open("xorr.in")
l=f.read()
f.close()
s=l.split()
dlina=len(s)-1
i=0
def proverka(spisok):
	past=[]
	for q in spisok:
		if q not in past:
			if spisok.count(q)%2!=0:
				return str(q)
			else:
				past.append(q)
otvet=""
while i!=dlina:
	start=int(s[i])+1
	otvet=otvet+proverka(s[i+1:i+start:])+"\n"
	i+=start
f=open("xorr.out","w")
f.write(otvet)
f.close()

Но он все равно медленный!!!

fata1ex

Апрель 17, 2012 00:02:52

Зачем просить о помощи, если нет желания её получать?
Попробуйте:

sequences = [[1,1,2,3,4,3,4], [2,2,3,3,4,4,4,2,2,1,1], [1,2,2,3,3,3,4,4,4,4,3]]
result = []
for seq in sequences:
	occurrences = dict()
	for number in seq:
		if number in occurrences:
			occurrences[number] += 1
		else:
			occurrences.update({number:1})
	for number in occurrences:
		if occurrences[number] % 2:
			result.append(number)
			break
print result

Не бог весть что, но результат меньше 2 секунд при

sequences = [[1,1,2,3,4,3,4]*101, [2,2,3,3,4,4,4,2,2,1,1]*101, [1,2,2,3,3,3,4,4,4,4,3]*101]*1000

Ну и линейная сложность, поэтому при увеличении размера последовательностей в 10 раз мы получаем ~20 секунд. У вас же при росте подпоследовательности сложность растет квадратично (так как вы ищете методом list.count, который, скорее всего, сравнивает каждый элемент с каждым).

fata1ex

Май 1, 2012 10:55:30

Наткнулся на тему, сделал более аккуратный вариант, который работает не намного медленнее:

sequences = [[1,1,2,3,4,3,4]*101, [2,2,3,3,4,4,4,2,2,1,1]*101, [1,2,2,3,3,3,4,4,4,4,3]*101]*1000
result = []
 
for seq in sequences:
	occurrences = set()
	for number in seq:
		if number in occurrences:
			occurrences.remove(number)
		else:
			occurrences.add(number)
 
	result.append(occurrences.pop())
 
print result

fata1ex

Май 2, 2012 15:27:57

Эта тема преследует меня.

Вспомнил про батареечное решение:

from collections import Counter
  
sequences = [[1,1,2,3,4,3,4]*101, [2,2,3,3,4,4,4,2,2,1,1]*101, [1,2,2,3,3,3,4,4,4,4,3]*101]*1000
result = []
 
for seq in sequences:
	counter = Counter(seq)
        # or result.append([num for num in counter if counter[num] % 2])
	for num in counter:
		if counter[num] % 2:
			result.append(num)
			break  
   
print result

Оно почему-то заметно медленнее.

Так побыстрее:

from collections import Counter 
            
cache = dict()
def my_counter(idx):
	try:
		return cache[idx]
	except KeyError:
		cache[idx] = Counter(seqs[idx])
		return cache[idx] 
                     
seqs = [[1,1,2,3,4,3,4]*101, [2,2,3,3,4,4,4,2,2,1,1]*101, [1,2,2,3,3,3,4,4,4,4,3]*101]*1000
print [ num for idx in xrange(len(seqs)) for num in my_counter(idx) if my_counter(idx)[num] % 2 ]

SOUR

Май 9, 2012 16:24:52

fata1ex
Try Execept работает быстрей if.

p.s. пруф где-то на хабре :)

FishHook

Май 10, 2012 09:14:08

SOUR
fata1ex
Try Execept работает быстрей if.

p.s. пруф где-то на хабре :)

Не будем верить на слово вражьему ресурсу, проверим сами

from timeit import Timer
d=dict(enumerate(range(1000000)))
func1="""def foo():
	    for i in xrange(0,10000000):
		if d.get(i):pass
		else: pass
      """
func2="""def foo():
	    for i in xrange(0,10000000):
		try: d[i]
		except KeyError: pass
      """
      
t = Timer(stmt=func1)
t2 = Timer(stmt=func2)
print "if %s usec/pass" % t.timeit(number=1000000)
print "try %s usec/pass" % t2.timeit(number=1000000)

if 0.0694398880005 usec/pass
try 0.0692939758301 usec/pass

И правда быстрее

Chern

Май 10, 2012 09:25:42

Покажу фокус:

>>> from timeit import Timer
>>> d=dict(enumerate(range(1000000)))
>>> func1="""def foo():
...         for i in xrange(0,10000000):
...             if i in d: d[i]
...             else: pass
...       """
>>> 
>>> func2="""def foo():
...         for i in xrange(0,10000000):
...             try: d[i]
...             except KeyError: pass
...       """
>>> t = Timer(stmt=func1)
>>> t2 = Timer(stmt=func2)
>>> print "if %s usec/pass" % t.timeit(number=1000000)
if 0.0738561153412 usec/pass
>>> print "try %s usec/pass" % t2.timeit(number=1000000)
try 0.0838830471039 usec/pass