challenge ファイル内の重複行削除(後優先)

アレイのuniq」の応用編です。

入力されたテキストデータから重複する行をとりのぞいて、その結果を標準出力へ出力するプログラムを作成してください。

重複行の排除については、以下の仕様を満たしてください。

  1. 読み込み順序は変更しないこと
  2. 重複する行があった場合、以前のデータを削除すること (後に読み込んだ方が強い)
  3. ファイル全体を一度にメモリに読み込んで処理しないこと
  4. 比較は行全体で行うこと

#4.はおまけですがある/なしで作りが変わってくると思われるので追加しました。


この問題はraynstardさんにご投稿いただきました。ご協力ありがとうございます。 ところで、素朴な実装のしかたをするとメモリ容量の数倍のサイズのすべての行が異なっているファイルを読ませたときに大変なことが起こりそうな気がしますが、そういうシビアなお題設定ではないので素朴に解いてしまって構いません。シビアなのは続編にしたいと思います。

Posted feedbacks - Nested

Flatten Hidden
ナイーブ。文字エンコードはUTF8。とりあえず、
標準入力 → 標準出力
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
module Main where

import Control.Applicative
import qualified Data.Set as S
import qualified System.IO.UTF8 as U

main :: IO ()
main = mapM_ (U.putStrLn . snd)
     . S.toAscList . S.map pair
     . foldl ((S.insert <*>) . flip S.delete) S.empty
     . zipWith N [1..] . lines =<< U.getContents
  where pair (N i s) = (i,s)

data NL = N Int String
instance Eq NL where
  N _ s == N _ s' = s == s'
instance Ord NL where
  N _ s `compare` N _ s' = s `compare` s'
ううむ。条件3を満していない気がする。
メモリの全部読み込み終ってから、次の処理をしているわけではないけど、
入力したデータの処理が全部済んでからでないと出力できないわけで、
重複がなければ結局全部メモリに読み込むことになる。

> 重複がなければ結局全部メモリに読み込むことになる。

「重複が全くないケースにメモリに全部読み込まれないようにせよ」という条件をつけると難易度が跳ね上がりますね。 なので条件3はゆるめに解釈するつもりでした。

素朴に
 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
#include <list>
#include <string>
#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>
using namespace std;

void uniq(const char *fname) {
	ifstream fin(fname);
	if (!fin) return;
	
	list<string> lines;
	string s;
	
	while (getline(fin, s)) {
		lines.remove(s);
		lines.push_back(s);
	}

	copy(lines.begin(), lines.end(), ostream_iterator<string>(cout, "\n"));
}

int main(void) {
	uniq("hoge.txt");
	return 0;
}
3.ファイル全体を一度にメモリに読み込んで処理しないこと

これにひっかかっていませんか?
申し訳ありません。
全く問題ないと思います。
(多分続編と間違えてました)
Squeak Smalltalk で。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
| in lines line out |
in := FileStream oldFileNamed: 'in.txt'.
lines := OrderedCollection new.

[(line := in nextLine) notNil] whileTrue: [
	lines remove: line ifAbsent: [].
	lines add: line].
in close.

out := FileStream forceNewFileNamed: 'out.txt'.
lines do: [:each | out nextPutAll: each; cr].
out edit
素朴に最初に思い付いたままな感じで…。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
(defpackage #:doukaku-66 (:use #:cl #:pg))

(in-package #:doukaku-66)

(defun no-dup (file &optional (output t))
  (with-open-file (input file :direction :input)
    (flet ((rl () (read-line input nil 'eof)))
      (do ((line (rl) (rl))
	   result)
	  ((eql 'eof line)
	   (mapc (lambda (l) (format output "~&~A~%" l))
		 (delete nil (nreverse result))))
	(aif (member line result :test #'string=)
	     (setf (car it) nil))
	(push line result)))))
思いつくままに。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
fun uniq file =
let
  open TextIO

  val fs = openIn file

  fun f a =
    case inputLine fs of
        NONE => app print a
      | SOME s => f ((List.filter (fn x => x <> s) a) @ [s])
in
  f []
end;

uniq "hoge.txt"
素朴な疑問ですが。 仕様2の「重複する行があった場合、以前のデータを削除すること (後に読み込んだ方が強い) 」ですが、まったく同じ内容の行なので、どちらを削除しても結果は同じになるのではないのでしょうか?(メモリの物理領域は違うでしょうが・・・・) 続編に何かあるという事でしょうか?
その重複する行が表れる場所が違うと思います。
後出現優先であれば、
A
B
A
C
A
↓
B
C
A
これが、先に出てくる方が優先であれば
↓
A
B
C
になるでしょう。
なるほど、検討不足でした。
ひさしぶりの投稿。
1
2
3
4
5
6
7
8
(use srfi-1)
(use srfi-42)
(define (uniq-file file)
  (call-with-input-file file
    (lambda (p)
      (let1 ls (fold-ec '() (:port ln p read-line)
                        ln (lambda (x r) (append (delete! x r) (list x))))
        (do-ec (: ln ls) (print ln))))))
port-fold がありました。
1
2
3
4
5
(use srfi-1)
(define (uniq-file file)
  (define (rp ls) (unless (null? ls) (rp (cdr ls)) (print (car ls))))
  (with-input-from-file file
    (lambda () (rp (delete-duplicates (port-fold cons '() read-line))))))
とりあえず。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import sys

l = []
for s in file(sys.argv[1], 'r') if len(sys.argv) > 1 else sys.stdin:
  try:
    l.remove(s)
  except:
    pass
  l.append(s)

for s in l:
  sys.stdout.write(s)
うわー、なるほど、試しに消してみるわけですね。
その発想はなかったです。

僕なら「前のを消す」じゃなくて「後ので上書き」ってやるかな。
辞書を使って。
1
2
3
4
5
6
7
8
import sys
in_stream = file(sys.argv[1], 'r') if len(sys.argv) > 1 else sys.stdin
d = {}
for i, line in enumerate(in_stream):
    d[line] = i

for line in sorted(d, key=d.__getitem__):
    sys.stdout.write(line)
簡潔さ最優先で書きました。
1
2
(loop for s = (read-line nil nil) while s collect s into lines
  finally (mapc #'write-line (delete-duplicates lines :test #'string=)))
LinkedHashSetを使用しました。後の行を優先するために先に読んだ行を消去しています(入力は標準入力から与えます)。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import java.io.*;
import java.util.*;

public class Sample {
    public static void main(String[] args) throws IOException {
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        LinkedHashSet<String> uniqLines = new LinkedHashSet<String>();
        String str;
        while ((str = r.readLine()) != null) {
            if (uniqLines.contains(str)) {
                uniqLines.remove(str);
            }
            uniqLines.add(str);
        }
        for (String s : uniqLines) {
            System.out.println(s);
        }
    }
}
冒頭のarglみたいな手続き欲しいです。
1
2
3
4
5
6
7
8
(define (argl proc) (lambda arg (proc arg)))

(let ((h (make-hash-table 'string=?))
      (c 0))
  (port-for-each (cut hash-table-put! h <> (inc! c)) read-line)
  (for-each (compose print car)
            (sort (hash-table-map h cons)
                  (compose (apply$ <) (argl (map$ cdr))))))
> arglみたいな手続き欲しいです

結局composeするなら
  (compose (apply$ <) (map$ cdr) list)
でもいけますよ。

Schemeの場合、そこまでしてポイントフリーにしても
あまり簡潔にならないし、動的型なんでオーバヘッドも
大きくなる (引数の数がわからないから全部いちいち
リストにパックして受け渡すことになる)などメリットが
あまりないとも言えますが。こっちの方が短くなっちゃう:
  (lambda (a b) (< (cdr a) (cdr b)))

>  (lambda (a b) (< (cdr a) (cdr b)))

そうですね。実行効率を考えても、こちらの方がよいとは思います。文字数も少ないです。わかりやすいとも思います。ただまあ、「両方のcdrを比較する」ってことばで説明できるのに、cdrが二回出てくるのが許せなかっただけなんです。
むしろ比較のキー抽出手続きを別に指定できるようにすべきかなあ。
そうですね。group-sequenceみたいに指定できると、ほとんどの場合に対応できそうです。
出来ないケースは、いくつかのキーが内在していて、キーの大小に優先順位があって、
それを単純な数値や文字列に写像出来ない
ような場合でしょうか。

場違いですみません。
getLinesで返ってくるのはイテレータです。
念のため。
1
2
3
4
5
6
import scala.collection.mutable.LinkedHashSet
import scala.io.Source.fromFile

(new LinkedHashSet[String] /: fromFile("test.txt").getLines){(set,line) =>
  set -= line; set += line; set
}.foreach(print)
1.入力文字をキーにして値を配列の位置を記憶。
2.存在してたらその位置にある配列の文字を空白にしておく。
3.ループ抜けたら空白を無視して出力。

※ちなみに改行コードも含めてキーとなるので、空白行が入力されてもその行はちゃんと空白行として出力されます。
1
2
3
$c=0;
while(<>){$b{$_}ne''?$r[$b{$_}]='':0;$b{$_}=$c++;push@r,$_}
print grep{$_}@r;
素朴?
標準入力→標準出力
1
2
3
4
5
6
7
<?php
$a=array();
for($i=0;($str=fgets(STDIN))!==false;)
	$a[$str]=$i++;
asort($a);
echo implode("",array_keys($a));
?>
仕様をそのまま書いた感じです
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
a = []

while line = ARGF.gets
  a.delete(line)
  a << line
end

a.each{|line|
  print line
}
上のは見た目は良いのですが
実際走らせるとa.deleteの部分がやばいことになるので
効率を若干考慮したバージョン。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
h = {}

while line = ARGF.gets
  h[line] = ARGF.lineno
end

h.sort_by{|line, lineno|
  lineno
}.each{|line, lineno|
  print line
}
Perlで書いてみた。
 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
my $file_name = $ARGV[0];

open IN , '<' , $file_name or die "Can't open $file_name";
open CMP, '<' , $file_name or die "Can't open $file_name";

my $hash = {};
my $index= {};

for (my $n=0; my $line = <IN>; $n++ )
{
    next if (exists $hash->{$n});

    my @array = ();
    for ( my $i=0; my $cmp = <CMP> ; $i++ )
    {
        if ( $line eq $cmp )
        {
            $hash->{$i} = undef ;
            push @array , $i;
        }
    }
    seek CMP , 0 , 0 ;

    my $tmp = (sort {$b <=> $a} ( @array ))[0];
    $index->{$tmp} = undef ;
}

for (my $i=0; my $line = <CMP>; $i++)
{
    print $line if (exists $index->{$i});
}

close IN ;
close CMP;

	
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import System (getArgs)
import System.IO
import System.IO.UTF8 as U
import Data.List ((\\))
import Control.Exception (bracket)

main = do
  (file:_) <- getArgs
  bracket (openFile file ReadMode) hClose exec

exec :: Handle -> IO ()
exec = loop []
  where loop ret h = do
          eof <- hIsEOF h
          if eof then U.print ret
                 else U.hGetLine h >>= return . (\l -> (ret \\ [l]) ++ [l]) >>= flip loop h
 join() で未定義属性は空文字列になることを利用。
1
2
3
4
var o = [], l = 0;
with(WSH.stdIn) while(!atEndOfStream) o[readLine() +'\n'] = l++;
for(l in o) o[o[l]] = l;
WSH.stdOut.write(o.join(''));
ども、raynstardです。
ネタばらすと元ネタは.bash_historyの内容整理で
ええ。イレギュラーなんて考えていませんでした(笑

実際には部分一致での比較にしているのでもう一手間かかっていますが
こんな感じでつかっています。

大きなファイルきたらどうなるんだろうちょっと怖い作りかも
# 入力ファイルはもちろん「|」で手抜き^^;
1
perl -ne '$h{$_}=++$i; END { print "$_" foreach ( sort { $h{$a} <=> $h{$b};} keys(%h));}'
> ところで、素朴な実装のしかたをするとメモリ容量の数倍のサイズの
> すべての行が異なっているファイルを
> 読ませたときに大変なことが起こりそうな気がしますが、
> そういうシビアなお題設定ではないので素朴に解いてしまって構いません。
> シビアなのは続編にしたいと思います。 
後編がこわいですなー(笑
2GBファイルとかっすか!
うーん、マージソートが必要になったりして?
使い方: sh uniq.sh input.txt

「シビア」な場合に想定される「DBMSの再発名」の準備です。#3のメモリは主記憶と解釈しました。
キャッシュで済んでしまうくらい小さいデータセットの場合にはこの解釈でも問題になるわけですが、
そのことを明示しているわけではないということで

uniq.shの内容は下に
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
mysql -uroot -p -N test << EOF

DROP TABLE IF EXISTS tmp;
CREATE TABLE tmp (
  id INT PRIMARY KEY AUTO_INCREMENT,
  line LONGTEXT NOT NULL
) CHARACTER SET UTF8;

LOAD DATA LOCAL INFILE "$1" INTO TABLE tmp FIELDS TERMINATED BY '\n' (line);

SELECT line FROM tmp GROUP BY line ORDER BY MAX(id);

EOF
mysql -uroot -p -N -r test << EOF

「-r」が必要です(エスケープ文字をそのまま出すために)
これ先優先になりますよね。
題意を満たせないと思います。
行データをメモリに保持してていいという条件だと理解
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Dictionary<string, long> table = new Dictionary<string, long>();
long number = 0L;
TextReader reader = args.Length > 0 ? new StreamReader(args[0], Encoding.Default) : Console.In;
string line = null;
while ((line = reader.ReadLine()) != null)
  table[line] = number++;
SortedDictionary<long, string> list = new SortedDictionary<long, string>();
foreach (KeyValuePair<string, long> pair in table)
  list.Add(pair.Value, pair.Key);
foreach (KeyValuePair<long, string> pair in list)
  Console.WriteLine(pair.Value);

続・ファイル内の重複行削除よりも制限が緩いので、これで充分かと。

Dan the One-Liner Monger

1
'print reverse do{grep {1>$s{$_}++} reverse <>}' ~/.bash_history
Cでは1行読み込むといったことでさえ満足に行えないため、1行の文字数制限と、行数制限を無くする(もちろんメモリの許す限り)というところで素朴に書くというレベルを超えています。
そのかわり、行の削除は非常に素朴です。というか、疲れました。
こればかりは、他の言語に出番を許すしかないのでしょうか。C++でさえあれば・・・!
 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BLOCK_SIZE 1024

void read_line(char **out){
    int cnt = 1;
    *out = (char *)malloc(1);
    *out[0] = '\0';
    do{
        *out = (char *)realloc(*out, BLOCK_SIZE * cnt);
        fgets((*out) + strlen(*out), BLOCK_SIZE, stdin);
        cnt++;
    }while((*out)[strlen(*out)-1] != '\n' && !feof(stdin));
    *out = (char *)realloc(*out, strlen(*out) + 1);
}

int main(){
    int i;
    int size = 0;
    char **list = NULL;
    char *line;
    while(!feof(stdin)){
        read_line(&line);
        for(i=0; i<size; i++){
            if(list[i]