중복되지 않는 7자리의 숫자들이 한줄 씩 나열된 파일이 있다.
파일안에는 총 1천만개까지 숫자가 있을 수 있다고 한다. (n < 107)
예)
3123889
0000007
1000001
4123789
... 생략 ...
이 파일안의 숫자를 순서대로 소트된 결과를 파일로 저장하는 프로그램을 만드시오.
도전과제 : 1MB 이하의 메모리만 사용하여 위 프로그램을 만드시오.
23개의 풀이가 있습니다.
from bitarray import bitarray
import random
import sys
def make_test_file(filename):
a = [i for i in range(10000000)]
random.shuffle(a)
f = open(filename, 'w')
for i in a:
f.write(format(i,'07d')+'\n')
f.close()
def big_file_sort(filename):
a = bitarray(10000000)
a.setall(False)
print "a is %s bytes." % sys.getsizeof(a)
for line in open(filename):
a[int(line)] = True
f = open("result.txt", 'w')
for i, v in enumerate(a):
if v:
f.write(format(i,'07d')+'\n')
f.close()
#make_test_file("test.txt")
big_file_sort("test.txt")
7자리 숫자에 중복이 없으므로 1천만건짜리 비트 배열로 풀어보았습니다.
최초 1천만건짜리 테스트 데이터를 생성한 후 파이썬의 bitarray를 이용해 보았습니다.
#sort.py
import random
def m_file (file) :
arr=[]
while len(arr) < 1000 :
ran=random.randint(0,10**7)
if ran not in arr :
arr.append(ran)
f=open(file,"w")
for num in arr :
f.write(format(num,'07d')+'\n')
f.close()
def f_open (file) :
arr=[]
f=open(file)
lines=f.readlines()
f.close()
for line in lines :
arr.append(int(line))
arr.sort()
return arr
def print_list(arr) :
for num in arr :
print (format(num,'07d'))
m_file("test.txt")
print_list(f_open("test.txt"))
Java 입니다
randomNumber.txt 라는 입력 파일이 존재한다고 가정
import java.io.*;
import java.util.*;
public class BitmapSort {
public static void main(String[] args) {
int[] num = new int[10000000]; // 데이터를 넣을 배열 생성
BitSet bitSet = new BitSet(10000000); // 정렬을 위한 비트셋
bitSet.clear(); // 비트셋 초기화 false 세팅
try {
File myFile = new File("randomNumber.txt");
BufferedReader reader = new BufferedReader(new FileReader(myFile));
// 데이터 파일 읽기
int j=0;
String line = null;
while ( (line = reader.readLine()) != null ) {
StringTokenizer tokenizer = new StringTokenizer(line);
num[j] = Integer.parseInt (tokenizer.nextToken() );
bitSet.set(num[j], true);
// num[j] 의 값이 bitSet 의 인덱스로
j++;
}
reader.close();
File file = new File("sortedNumber.txt");
BufferedWriter writer = new BufferedWriter(new FileWriter(file));
// 파일 출력
for ( int k=0 ; k<bitSet.length() ; k++ ) {
if ( bitSet.get(k) ) { // bitSet 값이 true 일때만 파일에 쓰기
writer.write(Integer.toString(k));
writer.newLine();
}
}
writer.close();
} catch (IOException ex) { ex.printStackTrace(); }
}
}
생각하는 프로그래밍 문제네요. 이거 자바로 풀었던거 올립니다.
데이터 생성 로직도 있습니다만 생략 합니다.
http://pearlstyle.tistory.com/31
파이썬 3.2.5 기준입니다.
fin = open('숫자.txt')
number_list = []
for line in fin:
number_list.append(line.strip())
number_list.sort()
open('숫자소트.txt',mode='w').write("\n".join(number_list))
public class Sorter {
public static void main(String[] args) {
boolean[] num = new boolean[10000000];
try {
File input = new File("input.txt");
BufferedReader reader = new BufferedReader(new FileReader(input));
String str = "";
while((str = reader.readLine()) != null) {
num[Integer.parseInt(str)] = true;
}
reader.close();
File output = new File("output.txt");
BufferedWriter writer = new BufferedWriter(new FileWriter(output));
for(int i = 0; i < num.length; i++) {
if(num[i]) {
writer.write(new String().format("%07d\r\n", i));
}
}
writer.close();
} catch(IOException e) {
e.printStackTrace();
}
}
}
from bitarray import bitarray
ba = bitarray(10**7)
ba.setall(0)
for n in file('s444.txt'):
ba[int(n)]=1
f = open('s444_sorted.txt','w')
for i in range(len(ba)):
if ba[i] : f.write(format(i,'07d')+'\n')
f.close()
public class ddd {
public static final int Maximum=10000000;
HashSet<Integer> set;
ArrayList<Integer> list;
public static void main(String[] args) throws IOException {
ddd a=new ddd();
System.gc();
long preUseMemory=Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
try{
a.readFile();
a.createFile2();
}catch(Exception e){
e.printStackTrace();
}
long aftUserMemory=Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
long useMemory=(aftUserMemory-preUseMemory);
System.out.println(useMemory);
}
public void readFile() throws IOException{
list=new ArrayList<Integer>();
try{
File file=new File("d:/test.txt");
Scanner scan=new Scanner(file);
while(scan.hasNext()){
list.add(scan.nextInt());
}
}catch(Exception e){
e.printStackTrace();
}
Collections.sort(list);
}
public void createFile2() throws IOException{
PrintWriter pw=new PrintWriter("d:/move.txt");
Iterator hi =this.list.iterator();
while(hi.hasNext()){
pw.println(hi.next());
}
pw.close();
System.out.println("최종 정렬 파일 데이터 작성 종료");
}
}
죄송한데 제가 짠 코드가 1MB인지 확인할 방법으로 메인에서와 같은 방법으로 했는데 저게 맞나요? 제가볼때 저거는 이미 JVM에서 할당한 메모리를 파악하는것같은데 제가짠 코드의 메모리할당량이아닌... 100MB이상나오더라구요 제가 확인한 메모리 확인방식은..
이번 기회에 bitarray를 알게되었네요.
from bitarray import bitarray
b = bitarray(10**7)
with open('bigfile.txt', 'r') as f:
while True:
a = f.read(8)
if not a:
break
b[int(a.strip())] = 1
with open('result.txt', 'w') as g:
for i, v in enumerate(b):
if b:
g.write('{:07d}\n'.format(i))
Ruby
루비 bitset, 크리스탈 bit_array를 사용했습니다.
require 'bitset'
sort_by_bit = ->rf,wf,size,bs=Bitset.new(size) do
IO.foreach(rf) {|l| bs[l.to_i] = true }
File.open(wf,"w") {|f| (0...size).each {|i| f.puts(i) if bs[i] } }
end
#=> usage : sort_by_bit["unordered.txt", "sorted.txt", size]
Test
unordered_nums = [*0...100].shuffle # shuffle randomly
File.open("r.txt","w") {|f| unordered_nums.each {|n| f.puts(n) } }
sort_by_bit["r.txt", "w.txt",100]
generated_file_nums = File.read("w.txt").split.map(&:to_i)
# shuffled arr.sort == generated file's arr
expect( unordered_nums.sort ).to eq generated_file_nums
Crystal
require "bit_array"
def sort_by_bit(rf, wf, size)
ba = BitArray.new(size)
File.each_line(rf) {|l| ba[l.to_i] = true }
File.open(wf, "w") {|f| 0.upto(size-1) {|i| f.puts(i) if ba[i]} }
end
sort_by_bit("unordered.txt", "ordered.txt", 5)
Test
unordered_nums = (0...100).to_a.shuffle # shuffle randomly
File.open("r.txt","w") {|f| unordered_nums.each {|n| f.puts(n) } }
sort_by_bit("r.txt", "w.txt", 100)
generated_file_nums = File.read("w.txt").split.map(&.to_i)
# shuffled arr.sort == generated file's arr
unordered_nums.sort.should eq generated_file_nums
수가 천만개 이상 될 때면 선택정렬이 최적합이라 생각하고 선택정렬을 사용했습니다 또한 선택 정렬은 추가메모리가 필요 없는것으로 알고 있습니다
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_COLS 100
void main() {
FILE* in = fopen("input.txt", "rt");
FILE* out = fopen("output.txt", "wt");
char s[MAX_COLS];
char s1[MAX_COLS];
int min_range = 0;
while (fgets(s1,MAX_COLS,in)) {
int min = 100000000;
FILE* f = fopen("input.txt", "rt");
while(fgets(s,MAX_COLS,f)) {
int temp = atoi(s);
//printf("%d\n", temp);
if(min > temp && temp > min_range)
min = temp;
}
min_range = min;
char a[10];
itoa(min,a,10);
a[8] = '\0';
strcat(a,"\n");
fprintf(out, a);
}
}
import random
result,c = list(),0
while c != 10000000:
result.append('%07d' % c)
c += 1
random.shuffle(result)
F = open(r'C:\Users\Cyber\Desktop\file.txt','w')
F.write(' \n'.join(result))
F.close()
파일생성
F = open(r'C:\Users\Cyber\Desktop\file.txt','r')
_list = F.read().split('\n')
F.close()
F = open(r'C:\Users\Cyber\Desktop\file.txt','w')
F.write('\n'.join(sorted(_list)))
F.close()
#### 2017.02.04 D-383 ####
파일소트
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.BitSet;
import java.util.Scanner;
public class FileSort {
public static void main(String[] args) throws FileNotFoundException {
String path = FileSort.class.getResource("").getPath();
Scanner sc = new Scanner(new File(path + "FileSort.txt"));
PrintWriter pw = new PrintWriter(new File("FileSortResult.txt"));
BitSet bs = new BitSet(10000000);
while (sc.hasNext()) {
bs.set(sc.nextInt(), true);
}
sc.close();
bs.stream().forEach(b -> {
pw.println(b);
});
pw.close();
}
}
Python
메모리만 제한이니까 임시 파일 만들어서 기수정렬하면 될 거 같긴 한데 별로 하고 싶진 않네요-_-;
또는 0~1백만 사이 숫자만 읽어서 정렬하고, 1백만~2백만 사이 숫자만 읽어서 정렬하고, ... 이렇게 해도 되긴 될 것 같습니다.
그래도 비트맵이 제일 나은 듯
최대값이 10만 정도만 돼도 한 세월이라 크기를 줄여서 돌렸습니다.
# "길가의풀"님 컨닝(거의 똑같음)
import bit_array
import random
def make_testfile(filename, n):
nums = list(range(10000))
random.shuffle(nums)
f = open(filename, 'w')
for i in range(n):
f.write("%07d\n" % nums[i])
f.close()
def read_file(filename, bitarr):
f = open(filename, 'r')
line = f.readline()
while line:
bitarr[int(line)] = 1
line = f.readline()
f.close()
def write_file(filename, bitarr):
f = open(filename, 'w')
for i in range(bitarr.size):
if bitarr[i]:
f.write("%07d\n" % i)
f.close()
make_testfile('in.txt', 100)
bitarr = bit_array.BitArray(10000)
read_file('in.txt', bitarr)
write_file('out.txt', bitarr)
파이썬 3.6
import random
def makefile():
data = ''
with open("c:\\Python\\test_sort.txt", 'w') as f:
for i in range(1000000):
data = random.randint(1,10000000)
data = str(data)+"\n"
if len(data) != 8:
data = (8-len(data))*'0'+data
f.write(data)
def sort():
tmp = ''
with open("c:\\Python\\test_sort.txt", 'r') as f:
sort_list = f.read()
sort_list = sort_list.split("\n")
sort_list = sorted(sort_list)
del sort_list[0]
with open("c:\\Python\\test_sort_new.txt", 'w') as f:
for i in sort_list:
tmp = i + "\n"
f.write(tmp)
if __name__ == "__main__":
makefile()
sort()
def largesort(l):
def sorting(a, b):
result = 0
c = int(len(a)/2)
if not(len(a)-1):
if a[0] < b:
result += 1
else:
pass
elif b < a[c]:
result = sorting(a[:c], b)
else:
result = sorting(a[c:], b) + c
return result
result = [l[0]]
for i in range(1,len(l)):
result.insert(sorting(result,l[i]), l[i])
return result
#include <iostream>
#include <fstream>
using namespace std;
#define SIZE 10000
void QuickSort(int arr[], int left, int right)
{
int L = left, R = right;
int temp;
int pivot = arr[(left + right) / 2];
while (L <= R)
{
while (arr[L] < pivot)
L++;
while (arr[R] > pivot)
R--;
if (L <= R)
{
if (L != R)
{
temp = arr[L];
arr[L] = arr[R];
arr[R] = temp;
}
L++; R--;
}
if (left < R)
QuickSort(arr, left, R);
if (L < right)
QuickSort(arr, L, right);
}
}
int main()
{
int arr[SIZE], i = 0;
char getNum[8];
ifstream open("file.txt");
while (!open.eof())
{
open.getline(getNum, 8);
arr[i] = atoi(getNum);
i++;
}
open.close();
QuickSort(arr, 0, i - 1);
ofstream write("output.txt");
for (int j = 0; j < i; j++)
{
write << arr[j] << endl;
}
write.close();
return 0;
}
처음에는 5만개씩 잘라서 정렬하고 tmp파일에 저장하는 방식을 생각했었는데....(파이썬에서 5만개 리스트가 약 1메가 차지하더군요)
비트맵 정렬 배워갑니다
bitarray가 아니라 직접 2진법으로 구현했는데 반복문 2천만번 장난 아니네요...결과는 포기합니다;;
bit = 0
for i in open(inpath,'r',encoding='utf8'):
bit += 2**int(i)
with open(outpath,'w',encoding='utf8') as out:
i = 0
while bit > 0:
if bit%2 == 1: print('{:07}'.format(i),file=out)
bit = bit//2
i += 1
package test;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class test {
public static void main(String[] args) {
String path = "파일경로";
Scanner sc = null;
ArrayList<Integer> num = new ArrayList<>();
try {
sc = new Scanner(new File(path));
while (sc.nextLine() != null) {
num.add(sc.nextInt());
}
Collections.sort(num);
} catch (FileNotFoundException e) {
} finally {
sc.close();
}
FileWriter fw = null;
try {
fw = new FileWriter(new File(path));
for (int i = 0; i < num.size(); i++) {
fw.write(num.get(i) + "\r\n");
}
fw.flush();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
from bitarray import
aa = bitarray(10000000)
aa.setall(0)
ff=open('aa.txt','r')
lines = ff.readlines()
for n in lines:
n=n.split('\n')
aa[int(n[0])] = True
ff.close()
f = open('sorted_aa.txt','w')
for i in range(10000000):
if aa[i]:
f.write(format(i,'07d')+'\n')
f.close()
Python 3
seg_size)만큼씩 읽어서seg_file)로 저장heapq - merge (여러 정렬된 입력을 단일 정렬된 출력으로 병합)import itertools
import heapq
import contextlib
import os
def main():
inputfile = "./input.txt" # 정렬할 파일 경로
outputfile = "./output.txt" # 정렬된 파일 경로
seg_size = 5000 # 입력 파일에서 한 번에 읽어올 라인 수
seg_files = [] # 부분 정렬된 파일의 목록
with open(inputfile, "r") as fi:
# seg_id: 부분 정렬된 파일을 저장할 식별자
for seg_id in itertools.count(1):
# 입력 파일로부터 seg_size 만큼씩 자료를 읽어서 정렬함
partially_sorted = sorted(itertools.islice(fi, seg_size))
if not partially_sorted: # EOF
break
seg_file = f"./seg_{seg_id}.txt" # 부분 정렬된 파일명
seg_files.append(seg_file)
with open(seg_file, "w") as fo:
fo.writelines(partially_sorted)
# https://stackoverflow.com/questions/26240228/how-to-join-multiple-sorted-files-in-python-alphabetically
with contextlib.ExitStack() as stack:
files = [stack.enter_context(open(seg_file)) for seg_file in seg_files]
with open(outputfile, "w") as fo:
fo.writelines(heapq.merge(*files))
# 부분 정렬 파일 삭제
for seg_file in seg_files:
os.remove(seg_file)
if __name__ == "__main__":
main()
from random import *
file = open('C:\Python\memo.txt','w')
for k in range(1000):
a = str(randint(1000000,9999999))
file.write(a)
file.write('\n')
file.close()
file = open('memo.txt','r')
r = file.read().split('\n')
file.close()
r.remove('')
arr =sorted(list(map(int,r)))
file = open('memo.txt','w')
for k in arr:
file.write(str(k))
file.write('\n')
file.close()
숫자를 정렬하는건 어렵지 않은데.. 메모리 사용량을 어떻게 알수있는지는.. 공부가 필요합니다 ㅜ
def isLarge(su, value):
for i in range(7):
if su[i] < value[i]:
return True
elif su[i] > value[i]:
return False
return False
def writeFile(filename, lst):
f = open(filename, 'w')
for i in range(len(lst)-1):
if lst[i]:
f.write(lst[i])
f.close()
f = open('data.txt', 'r')
line = [x for x in f.readlines()]
lst = ['9999999']
for val in line:
N = len(lst)
for i in range(len(lst)):
if isLarge(val, lst[i])==True:
lst.insert(i, val)
break
f.close()
write_file('result.txt', lst)
print('end!!')