DjangoBB LoFi version

Полная версия: сортировка большого объема данных в текстовом файле

Начало » Python для новичков » сортировка большого объема данных в текстовом файле

1 2 3

o7412369815963

Окт. 21, 2010 23:32:55

o7412369815963
Zubchick
питончую сортировку слияниями :) http://algolist.manual.ru/sort/faq/q10.php

или сильно оптимизированный вариант, но более сложная реализация http://algolist.manual.ru/sort/faq/q13.php
туфта и надувательство, эта ф-ия не делает ничего:
list-type mergesort (list-type L; int n)  { 
if (n = 1) return (L) else { 
    разделить L на две половины L1 и L2; 
    return (merge (mergesort (L1,n/2), mergesort (L2,n/2)) );
    } 
}
merge() - функция слияния.
и пример там не рабочий

merge() - функция слияния. - это не просто слияние, но и по сути сортировка, тогда все работает.

esal

Окт. 22, 2010 10:47:15

o7412369815963
o7412369815963
Zubchick
питончую сортировку слияниями :) http://algolist.manual.ru/sort/faq/q10.php

или сильно оптимизированный вариант, но более сложная реализация http://algolist.manual.ru/sort/faq/q13.php
туфта и надувательство, эта ф-ия не делает ничего:
list-type mergesort (list-type L; int n)  { 
if (n = 1) return (L) else { 
    разделить L на две половины L1 и L2; 
    return (merge (mergesort (L1,n/2), mergesort (L2,n/2)) );
    } 
}
merge() - функция слияния.
и пример там не рабочий
merge() - функция слияния. - это не просто слияние, но и по сути сортировка, тогда все работает.

Вот в качестве примера сортировки файла с 1000 чисел типа double(сортировка слиянием, как описано тут http://algolist.manual.ru/sort/faq/q10.php) :

import time

def merge(left, right):
result =
i ,j = 0, 0
while i < len(left) and j < len(right):
if left <= right:
result.append(left)
i += 1
else:
result.append(right)
j += 1
result += left
result += right
return result

def mergesort(list):
if len(list) < 2:
return list
else:
middle = len(list) / 2
left = mergesort(list)
right = mergesort(list)
return merge(left, right)

def main():
t = time.time()
print ‘starting at %s’ % t

name = ‘1.txt’ #файл с 1000 строк их чисел
NUMS = #тут будет храниться отсортированный список
with open(name, “r”) as f:
for line in f:
NUMS.append(float(line.rstrip()))
print mergesort(NUMS)
basetime = time.time() - t #вычисляем время работы сортировки
print ‘file was sorted in %s secs’ % basetime

if __name__ == “__main__”:
main()

esal

Окт. 22, 2010 10:50:06

А кого нить есть пример (на python) многофазной сортировки слиянием для файлов? Теория есть и пример на С тоже (тут http://algolist.manual.ru/sort/faq/q13.php), но все же, если у кого нить есть пример на python поделитесь, пожалуйста?

pasaranax

Окт. 22, 2010 20:39:04

по-моему с такими объемами лучше субд использовать

esal

Окт. 22, 2010 21:30:48

pasaranax
по-моему с такими объемами лучше субд использовать

Хорошо, допустим СУБД. Предложите, пожалуйста, свой вариант на MySQL к примеру.

pasaranax

Окт. 22, 2010 23:18:49

Ну вот как-то так:

# -*- coding: utf-8 -*-

import MySQLdb

db = MySQLdb.Connect(user='root', passwd='111', db='test')
cur = db.cursor()

numbers = open('numbers.txt')
cur.execute('TRUNCATE TABLE `numbers`')
cur.executemany('INSERT INTO `numbers` SET `number`=%s', numbers)

numbers_sorted = open('numbers_sorted.txt', 'w+')
cur.execute('SELECT `number` FROM `numbers` ORDER BY `number`')
for row in cur.fetchall():
    numbers_sorted.write(str(row[0]) + '\n')

таблица:

CREATE TABLE `numbers` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `number` double DEFAULT NULL,
  KEY `id` (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=15 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

Zubchick

Окт. 22, 2010 23:24:43

радикально…

Окт. 23, 2010 10:58:08

esal
А кого нить есть пример (на python) многофазной сортировки слиянием для файлов?

Вот нечто похожее от автора языка:
http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html

pasaranax

Окт. 23, 2010 17:06:25

отсортировал через mysql миллион значений за 233 секунды, значит миллиард получится за 64 часа =D

Андрей Светлов

Окт. 23, 2010 20:29:43

Получится дольше - зависимость нелинейная.
“Классический” вариант - многопутевое слияние предварительно отсортированных небольших кусочков, насколько я это себе представляю.