Python实现选择排序的方法

Python实现大文件排序的方法,

本文实例讲述了Python实现大文件排序的方法。分享给大家供大家参考。具体实现方法如下:

import gzip
import os
from multiprocessing import Process, Queue, Pipe, current_process, freeze_support
from datetime import datetime
def sort_worker(input,output):
 while True:
  lines = input.get().splitlines()
  element_set = {}
  for line in lines:
    if line.strip() == 'STOP':
      return
    try:
      element = line.split(' ')[0]
      if not element_set.get(element): element_set[element] = ''
    except:
      pass
  sorted_element = sorted(element_set)
  #print sorted_element
  output.put('\n'.join(sorted_element))
def write_worker(input, pre):
  os.system('mkdir %s'%pre)
  i = 0
  while True:
    content = input.get()
    if content.strip() == 'STOP':
      return
    write_sorted_bulk(content, '%s/%s'%(pre, i))
    i += 1
def write_sorted_bulk(content, filename):
  f = file(filename, 'w')
  f.write(content)
  f.close()
def split_sort_file(filename, num_sort = 3, buf_size = 65536*64*4):
  t = datetime.now()
  pre, ext = os.path.splitext(filename)
  if ext == '.gz':
    file_file = gzip.open(filename, 'rb')
  else:
    file_file = open(filename)
  bulk_queue = Queue(10)
  sorted_queue = Queue(10)
  NUM_SORT = num_sort
  sort_worker_pool = []
  for i in range(NUM_SORT):
    sort_worker_pool.append( Process(target=sort_worker, args=(bulk_queue, sorted_queue)) )
    sort_worker_pool[i].start()
  NUM_WRITE = 1
  write_worker_pool = []
  for i in range(NUM_WRITE):
    write_worker_pool.append( Process(target=write_worker, args=(sorted_queue, pre)) )
    write_worker_pool[i].start()
  buf = file_file.read(buf_size)
  sorted_count = 0
  while len(buf):
    end_line = buf.rfind('\n')
    #print buf[:end_line+1]
    bulk_queue.put(buf[:end_line+1])
    sorted_count += 1
    if end_line != -1:
      buf = buf[end_line+1:] + file_file.read(buf_size)
    else:
      buf = file_file.read(buf_size)
  for i in range(NUM_SORT):
    bulk_queue.put('STOP')
  for i in range(NUM_SORT):
    sort_worker_pool[i].join()

  for i in range(NUM_WRITE):
    sorted_queue.put('STOP')
  for i in range(NUM_WRITE):
    write_worker_pool[i].join()
  print 'elasped ', datetime.now() - t
  return sorted_count
from heapq import heappush, heappop
from datetime import datetime
from multiprocessing import Process, Queue, Pipe, current_process, freeze_support
import os
class file_heap:
  def __init__(self, dir, idx = 0, count = 1):
    files = os.listdir(dir)
    self.heap = []
    self.files = {}
    self.bulks = {}
    self.pre_element = None
    for i in range(len(files)):
      file = files[i]
      if hash(file) % count != idx: continue
      input = open(os.path.join(dir, file))
      self.files[i] = input
      self.bulks[i] = ''
      heappush(self.heap, (self.get_next_element_buffered(i), i))
  def get_next_element_buffered(self, i):
    if len(self.bulks[i]) < 256:
      if self.files[i] is not None:
        buf = self.files[i].read(65536)
        if buf:
          self.bulks[i] += buf
        else:
          self.files[i].close()
          self.files[i] = None
    end_line = self.bulks[i].find('\n')
    if end_line == -1:
      end_line = len(self.bulks[i])
    element = self.bulks[i][:end_line]
    self.bulks[i] = self.bulks[i][end_line+1:]
    return element
  def poppush_uniq(self):
    while True:
      element = self.poppush()
      if element is None:
        return None
      if element != self.pre_element:
        self.pre_element = element
        return element
  def poppush(self):
    try:
      element, index = heappop(self.heap)
    except IndexError:
      return None
    new_element = self.get_next_element_buffered(index)
    if new_element:
      heappush(self.heap, (new_element, index))
    return element
def heappoppush(dir, queue, idx = 0, count = 1):
  heap = file_heap(dir, idx, count)
  while True:
    d = heap.poppush_uniq()
    queue.put(d)
    if d is None: return
def heappoppush2(dir, queue, count = 1):
  heap = []
  procs = []
  queues = []
  pre_element = None
  for i in range(count):
    q = Queue(1024)
    q_buf = queue_buffer(q)
    queues.append(q_buf)
    p = Process(target=heappoppush, args=(dir, q_buf, i, count))
    procs.append(p)
    p.start()
  queues = tuple(queues)
  for i in range(count):
    heappush(heap, (queues[i].get(), i))
  while True:
    try:
      d, i= heappop(heap)
    except IndexError:
      queue.put(None)
      for p in procs:
        p.join()
      return
    else:
      if d is not None:
        heappush(heap,(queues[i].get(), i))
        if d != pre_element:
          pre_element = d
          queue.put(d)
def merge_file(dir):
  heap = file_heap( dir )
  os.system('rm -f '+dir+'.merge')
  fmerge = open(dir+'.merge', 'a')
  element = heap.poppush_uniq()
  fmerge.write(element+'\n')
  while element is not None:
    element = heap.poppush_uniq()
    fmerge.write(element+'\n')
class queue_buffer:
  def __init__(self, queue):
    self.q = queue
    self.rbuf = []
    self.wbuf = []
  def get(self):
    if len(self.rbuf) == 0:
      self.rbuf = self.q.get()
    r = self.rbuf[0]
    del self.rbuf[0]
    return r
  def put(self, d):
    self.wbuf.append(d)
    if d is None or len(self.wbuf) > 1024:
      self.q.put(self.wbuf)
      self.wbuf = []
def diff_file(file_old, file_new, file_diff, buf = 268435456):
  print 'buffer size', buf
  from file_split import split_sort_file
  os.system('rm -rf '+ os.path.splitext(file_old)[0] )
  os.system('rm -rf '+ os.path.splitext(file_new)[0] )
  t = datetime.now()
  split_sort_file(file_old,5,buf)
  split_sort_file(file_new,5,buf)
  print 'split elasped ', datetime.now() - t
  os.system('cat %s/* | wc -l'%os.path.splitext(file_old)[0])
  os.system('cat %s/* | wc -l'%os.path.splitext(file_new)[0])
  os.system('rm -f '+file_diff)
  t = datetime.now()
  zdiff = open(file_diff, 'a')
  old_q = Queue(1024)
  new_q = Queue(1024)
  old_queue = queue_buffer(old_q)
  new_queue = queue_buffer(new_q)
  h1 = Process(target=heappoppush2, args=(os.path.splitext(file_old)[0], old_queue, 3))
  h2 = Process(target=heappoppush2, args=(os.path.splitext(file_new)[0], new_queue, 3))
  h1.start(), h2.start()
  old = old_queue.get()
  new = new_queue.get()
  old_count, new_count = 0, 0
  while old is not None or new is not None:
    if old > new or old is None:
      zdiff.write('< '+new+'\n')
      new = new_queue.get()
      new_count +=1
    elif old < new or new is None:
      zdiff.write('> '+old+'\n')
      old = old_queue.get()
      old_count +=1
    else:
      old = old_queue.get()
      new = new_queue.get()
  print 'new_count:', new_count
  print 'old_count:', old_count
  print 'diff elasped ', datetime.now() - t
  h1.join(), h2.join()

希望本文所述对大家的Python程序设计有所帮助。

本文实例讲述了Python实现大文件排序的方法。分享给大家供大家参考。具体实现方法如下:
import gzipimport o…

选择排序:

Python实现针对中文排序的方法,

本文实例讲述了Python实现针对中文排序的方法。分享给大家供大家参考,具体如下:

Python比较字符串大小时,根据的是ord函数得到的编码值。基于它的排序函数sort可以很容易为数字和英文字母排序,因为它们在编码表中就是顺序排列的。

>> print ','< '1'<'A'<'a'<'阿'
True

但要很处理中文就没那么容易了。中文通常有拼音和笔画两种排序方式,在最常用中文标准字符集GB2312中,3755个一级中文汉字是按照拼音序进行编码的,而3008个二级汉字则是按部首笔画排列,

>> print '曙'< '鲑','曾'<'怡'
True True

出现这样的结果是因为‘曙’和‘曾’都是常用字,而‘鲑’和‘怡’都是次常用字,但无论从笔画还是拼音来看,这两对顺序都应该反过来。后来扩充的GBK和GB18030编码为了向下兼容,都没有更改之前的汉字顺序,于是sort之后的次序就很乱了。

另一方面unicode编码的中文是按《康熙字典》的偏旁部首和笔画数来排列的,所以排序结果和GB编码又不一样。

# encoding=utf8
char=['赵','钱','孙','李','佘']
char.sort()
for item in char:
  print item.decode('utf-8').encode('gb2312')

输出是:”佘孙李赵钱”;而保存成gb2312编码后

# encoding=gb2312
char=['赵','钱','孙','李','佘']
char.sort()
for item in char:
  print item

输出是:“李钱孙赵佘”。显然,这两个结果都不是我们想要的。那我们究竟怎样才能对中文正确排序呢?

先要弄清楚中文词典的排序规则:先按拼音排列,区分四声,拼音相同的就看笔画数目多少,笔画数也相同的再按笔顺中的具体笔划类型来区分,新华字典采用的顺序是一丨丿丶乙,也称作“天上人间”,应该没有笔划类型也完全一样的。所以中文排序不仅需要带音调的汉字拼音对照表,还需要有具体笔顺的数据。

本以为有现成的模块,试了几个都不理想。pyzh的转换代码只支持不到7千字,而且还没有音调。水木的roy的代码涵盖了2万多字符,但需要pysqlite支持……还是自立更生吧~

我找到最全的数据是slowwind9999上传到csdn的unicode汉字编码表(点击此处本站下载。),包括全部20902个汉字的全拼、五笔、郑码、UNICODE、GBK、笔画数
部首,以及笔顺编号(拼音部分没有音调,而且个别注音有误,如
囍,猤,啹等字,使用需注意。)我提取了其中的笔顺数据,又用江志键的“实用汉字转拼音”程序制作了unicode汉字音调版,其中中文汉字用四声标注,319个日韩汉字没有音调以示区别,并根据汉典的数据略作修正(但仍可能存在错误)。有了这两个对照表,下面的工作就简单了。

# 建立拼音辞典
dic_py = dict()
f_py = open('py.txt','r')
content_py = f_py.read()
lines_py = content_py.split('\n')
n=len(lines_py)
for i in range(0,n-1):
  word_py, mean_py = lines_py[i].split('\t', 1)
  dic_py[word_py]=mean_py
f_py.close()

笔顺字典的处理方法也完全相同,虽然文本有两万行,导入还是很快的,0.5秒左右。如果把这两个文件合并起来统一处理,应该可以更快。

# 辞典查找函数
def searchdict(dic,uchar):
  if isinstance(uchar, str):
    uchar = unicode(uchar,'utf-8')
  if uchar >= u'\u4e00' and uchar < = u'\u9fa5':
    value=dic.get(uchar.encode('utf-8'))
    if value == None:
      value = '*'
  else:
    value = uchar
  return value

查找中文,一律转为UTF8字符串,汉字外的其他字符不做处理,原样输出。如果需要声母,只输出拼音的第一个字符就是了。只要资料准确,比较起来就很轻松了。数字在字母之前,爱(ai4)便会比昂(ang2)靠前,而笔顺值的位数代表了笔画数,数值对应笔划权重,直接比较数字大小就可以得到正确的顺序。代码如下:

#比较单个字符
def comp_char_PY(A,B):
  if A==B:
    return -1
  pyA=searchdict(dic_py,A)
  pyB=searchdict(dic_py,B)
  if pyA > pyB:
    return 1
  elif pyA < pyB:
    return 0
  else:
    bhA=eval(searchdict(dic_bh,A))
    bhB=eval(searchdict(dic_bh,B))
    if bhA > bhB:
      return 1
    elif bhA < bhB:
      return 0
    else:
      return 'Are you kidding?'
#比较字符串
def comp_char(A,B):
  charA = A.decode('utf-8')
  charB = B.decode('utf-8')
  n=min(len(charA),len(charB))
  i=0
  while i < n:
    dd=comp_char_PY(charA[i],charB[i])
    if dd == -1:
      i=i+1
      if i==n:
        dd=len(charA)>len(charB)
    else:
      break
  return dd
# 排序函数
def cnsort(nline):
  n = len(nline)
  lines='\n'.join(nline)
  for i in range(1, n): #插入法
    tmp = nline[i]
    j = i
    while j > 0 and comp_char(nline[j-1],tmp):
      nline[j] = nline[j-1]
      j -= 1
    nline[j] = tmp
  return nline

现在我们就可以按照字典的规范给中文排序了。

char=['赵','钱','孙','李','佘']
char=cnsort(char)
for item in char:
  print item.decode('utf-8').encode('gb2312')

终于得到了“李钱佘孙赵”,示例文件点此下载

这里我没有考虑多音字的情况。如果想让程序自动识别,可以增加多音词组对照表,通过上下文来判断。我不知道哪里有这样的数据,反正对于多音字不太多的情形,手动调整也就够了。

PS:这里再为大家推荐2款比较实用的相关在线排序工具供大家参考使用:

在线中英文根据首字母排序工具:

在线文本倒序翻转排序工具:

更多关于Python相关内容可查看本站专题:《Python正则表达式用法总结》、《Python数据结构与算法教程》、《Python
Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

本文实例讲述了Python实现针对中文排序的方法。分享给大家供大家参考,具体如下:
Python比较字符串大小…

本文实例讲述了Python实现按中文排序的方法。分享给大家供大家参考,具体如下:

本文实例讲述了Python实现分割文件及合并文件的方法。分享给大家供大家参考。具体如下:

选择排序(Selection sort)是一种简单直观的 排序算法
 。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

安装中文库

分割文件split.py如下:

Python 实现:

sudo apt-get update
sudo apt-get install language-pack-zh-hans-base
sudo dpkg-reconfigure locales
#!/usr/bin/python
##########################################################################
# split a file into a set of parts; join.py puts them back together;
# this is a customizable version of the standard unix split command-line 
# utility; because it is written in Python, it also works on Windows and
# can be easily modified; because it exports a function, its logic can 
# also be imported and reused in other applications;
##########################################################################
import sys, os
kilobytes = 1024
megabytes = kilobytes * 1000
chunksize = int(1.4 * megabytes)     # default: roughly a floppy
def split(fromfile, todir, chunksize=chunksize): 
 if not os.path.exists(todir):     # caller handles errors
  os.mkdir(todir)       # make dir, read/write parts
 else:
  for fname in os.listdir(todir):   # delete any existing files
   os.remove(os.path.join(todir, fname)) 
 partnum = 0
 input = open(fromfile, 'rb')     # use binary mode on Windows
 while 1:          # eof=empty string from read
  chunk = input.read(chunksize)    # get next part <= chunksize
  if not chunk: break
  partnum = partnum+1
  filename = os.path.join(todir, ('part%04d' % partnum))
  fileobj = open(filename, 'wb')
  fileobj.write(chunk)
  fileobj.close()       # or simply open().write()
 input.close()
 assert partnum <= 9999       # join sort fails if 5 digits
 return partnum
if __name__ == '__main__':
 if len(sys.argv) == 2 and sys.argv[1] == '-help':
  print 'Use: split.py [file-to-split target-dir [chunksize]]'
 else:
  if len(sys.argv) < 3:
   interactive = 1
   fromfile = raw_input('File to be split? ')  # input if clicked 
   todir = raw_input('Directory to store part files? ')
  else:
   interactive = 0
   fromfile, todir = sys.argv[1:3]     # args in cmdline
   if len(sys.argv) == 4: chunksize = int(sys.argv[3])
  absfrom, absto = map(os.path.abspath, [fromfile, todir])
  print 'Splitting', absfrom, 'to', absto, 'by', chunksize
  try:
   parts = split(fromfile, todir, chunksize)
  except:
   print 'Error during split:'
   print sys.exc_info()[0], sys.exc_info()[1]
  else:
   print 'Split finished:', parts, 'parts are in', absto
  if interactive: raw_input('Press Enter key') # pause if clicked

 

使用

合并文件join_file.py如下:

 代码如下

import locale
locale.setlocale(locale.LC_COLLATE, 'zh_CN.UTF8')
cmp = locale.strcoll
courses.sort(lambda x, y: cmp(x.course_name, y.course_name))
#!/usr/bin/python
##########################################################################
# join all part files in a dir created by split.py, to recreate file. 
# This is roughly like a 'cat fromdir/* > tofile' command on unix, but is 
# more portable and configurable, and exports the join operation as a 
# reusable function. Relies on sort order of file names: must be same 
# length. Could extend split/join to popup Tkinter file selectors.
##########################################################################
import os, sys
readsize = 1024
def join(fromdir, tofile):
 output = open(tofile, 'wb')
 parts = os.listdir(fromdir)
 parts.sort()
 for filename in parts:
  filepath = os.path.join(fromdir, filename)
  fileobj = open(filepath, 'rb')
  while 1:
   filebytes = fileobj.read(readsize)
   if not filebytes: break
   output.write(filebytes)
  fileobj.close()
 output.close()
if __name__ == '__main__':
 if len(sys.argv) == 2 and sys.argv[1] == '-help':
  print 'Use: join.py [from-dir-name to-file-name]'
 else:
  if len(sys.argv) != 3:
   interactive = 1
   fromdir = raw_input('Directory containing part files? ')
   tofile = raw_input('Name of file to be recreated? ')
  else:
   interactive = 0
   fromdir, tofile = sys.argv[1:]
  absfrom, absto = map(os.path.abspath, [fromdir, tofile])
  print 'Joining', absfrom, 'to make', absto
  try:
   join(fromdir, tofile)
  except:
   print 'Error joining files:'
   print sys.exc_info()[0], sys.exc_info()[1]
  else:
   print 'Join complete: see', absto
  if interactive: raw_input('Press Enter key') # pause if clicked

# selection_sort.py

测试用例

希望本文所述对大家的Python程序设计有所帮助。

defselection_sort(arr):

输入

您可能感兴趣的文章:

  • python读取LMDB中图像的方法
  • python读写LMDB文件的方法
  • python将多个文本文件合并为一个文本的代码(便于搜索)
  • Python实现将目录中TXT合并成一个大TXT文件的方法
  • python实现文本文件合并
  • python合并文本文件示例
  • python中合并两个文本文件并按照姓名首字母排序的例子
  • python 合并文件的具体实例
  • Python将多个excel文件合并为一个文件
  • 如何用Python合并lmdb文件

  count=len(arr)

# -*- coding: utf-8 -*-
import locale
#locale.setlocale(locale.LC_COLLATE, 'zh_CN.UTF8')
cmp = locale.strcoll
items = list('自挂东南枝'.decode('utf-8'))
print 'before'.center(10, '=')
print ''.join(items)
items.sort(lambda x, y: cmp(x, y))
print 'after'.center(10, '=')
print ''.join(items)

  foriinrange(count-1): # 交换 n-1 次

输出

    min=i

==before==
自挂东南枝
==after===
东挂南枝自

    # 找最小数

本机测试输出效果如下图:

    forjinrange(i, count):

图片 1

      ifarr[min] > arr[j]:

PS:这里再为大家推荐2款比较实用的相关在线排序工具供大家参考使用:

        min=j

在线中英文根据首字母排序工具:

    arr[min], arr[i]=arr[i], arr[min] # 交换

在线文本倒序翻转排序工具:

  returnarr

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python列表(list)操作技巧总结》、《Python数组操作技巧总结》、《Python字符串操作技巧汇总》、《Python函数使用技巧总结》、《Python入门与进阶经典教程》及《Python数据结构与算法教程》

 

希望本文所述对大家Python程序设计有所帮助。

my_list=[6,23,2,54,12,6,8,100]

您可能感兴趣的文章:

  • Python实现针对中文排序的方法
  • python
    中文乱码问题深入分析
  • python处理json数据中的中文
  • python实现中文输出的两种方法
  • Python中使用中文的方法
  • python
    sort、sorted高级排序技巧
  • python
    字典(dict)按键和值排序
  • python字符串排序方法
  • Python中对列表排序实例
  • python实现忽略大小写对字符串列表排序的方法

print(selection_sort(my_list))

 

原文链接:

相关文章