DouKaku?beta

challenge 擬似lsの実装 

スラッシュで区切られた文字列の配列(以下パスリスト)がある。
このパスリストにたいして擬似的なlsを行いたい。
lsはパスリストと表示対象ディレクトリのパスを入力する。

例としては以下のようになる。
pathList = ["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"]

ls(pathList,"aaa/")
>["bbb","ccc","ddd/"]

ls(pathList,"aaa/ddd/")
>["eee"]

なおパスリストが大きくなったとき、速度がなるべく低下しないように実装するのが望ましい。
文字列は任意の文字コードであると仮定してかまわない。
post comment

Posted feedbacks - Nested

Flatten Hidden
問題文からは、第2引数はディレクトリ名である (したがって ls(pathList, "aaa/bbb") は空リストとなる)  と読めるのですがそれでいいでしょうか。lsの動作を考えると単独ファイルにマッチする場合も許しても良さそうですが、一応ディレクトリ名のみ許すことにしました。

gosh> (ls '("aaa/bbb" "aaa/ccc" "aaa/ddd/eee" "ddd/bbb/eee") "aaa/")
("bbb" "ccc" "ddd/")
gosh> (ls '("aaa/bbb" "aaa/ccc" "aaa/ddd/eee" "ddd/bbb/eee") "aaa/ddd/")
("eee")
gosh> (ls '("aaa/bbb" "aaa/ccc" "aaa/ddd/eee" "ddd/bbb/eee") "aaa/ddd")
("eee")
gosh> (ls '("aaa/bbb" "aaa/ccc" "aaa/ddd/eee" "ddd/bbb/eee") "aaa/bbb")
()

lsにはリストが渡されるので、クレバーなデータ構造をls内で毎回作ってもあまり速度に貢献しないだろうと判断。文字列マッチで済ませています。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
(use srfi-1)
(use srfi-13)

(define (ls pathlist dir)
  (let* ((prefix (string-trim-right dir #[/]))
         (rx (string->regexp #`"^,(regexp-quote prefix)/")))
    (filter-map (lambda (p)
                  (and-let* ([m (rx p)])
                    (regexp-replace* (m'after) #/(?<=\/).*/ "")))
                pathlist)))

>クレバーなデータ構造をls内で毎回作ってもあまり速度に貢献しないだろうと判断。

次にデータ構造の話を出そうと思っていたんですが、
別の方がトピックで立ててくれたので、誘導してみる。

see: フォルダパス一覧のツリー構造への変換

odzさんの#4465の指摘を見て修正。

gosh> (ls '("aaa/bbb/ccc" "aaa/bbb/ddd" "aaa/ccc/zzz") "aaa")
("ccc/" "bbb/") 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
(use srfi-1)
(use srfi-13)

(define (ls pathlist dir)
  (let* ((prefix (string-trim-right dir #[/]))
         (rx (string->regexp #`"^,(regexp-quote prefix)/")))
    (fold (lambda (p rs)
            (or (and-let* ([m (rx p)]
                           [r (regexp-replace* (m'after) #/(?<=\/).*/ "")]
                           [ (not (member r rs)) ])
                  (cons r rs))
                rs))
          '() pathlist)))

毎回 pathList が変更されるのならこんな感じかなぁ．
pathList が固定なら最初に疑似的にディレクトリツリーを作成するんだけど．．．


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import Data.Maybe

ls :: [String] -> String -> [String]
ls fs p =  map g $ mapMaybe (f p) fs
 where f []     qs   = Just qs
       f (p:ps) (q:qs) 
         | p == q    = f ps qs
         | otherwise = Nothing
       g p = case break ('/'==) p of
               (p',"" ) -> p'
               (p',_:_) -> p'++['/']

やり方は多分 shiro さんと同じ。 プリプロセスありなら、内部でリストをソートするなりツリーを構築するなりするんだけど、リストを直接渡すという要求なら単純な手法かなぁ。 って、みんな思うことは一緒ですね。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import sys
import re
import itertools

def uniq(ls):
    return (k for k, g in itertools.groupby(ls))

def ls(pathList, dir):
    pat = re.compile('%s([^/]+/?)' % re.escape(dir))
    matches = itertools.ifilter(None, (pat.match(path) for path in pathList))
    return list(uniq(sorted([m.group(1) for m in matches])))

def main(args):
    pathList = 'aaa/bbb aaa/ccc aaa/ddd/eee bbb/ddd/eee'.split()
    print ls(pathList, 'aaa/')
    print ls(pathList, 'aaa/ddd/')

if __name__ == '__main__':
    main(sys.argv[1:])

縮めた感じで。

1
2
3
4
5
6
7
8
9
static void ls(string[] pathList, string path)
{
    int i;
    Console.WriteLine(
        pathList.Where( x => x.IndexOf(path) != -1 )
                .Select( x => x.Substring( path.Length, (i = x.IndexOf( "/", path.Length )) == -1 ? x.Length-path.Length : i-path.Length+1 ) )
                .Aggregate(new StringBuilder(), (sb, s) => sb.Append(s).Append(" "))
    );
}
C#2.0 で。new List<string> のあたりがもうちょっと何とかなりそうな気がするけど……。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
using System;
using System.Collections.Generic;
static class Program {
    static void Main() {
        string[] pathList = {"aaa/bbb", "aaa/ccc", "aaa/ddd/eee", "bbb/ddd/eee", "bbb/ddd/fff"};
        Console.WriteLine("[{0}]", string.Join(", ", Ls(pathList, "aaa/")));
        Console.WriteLine("[{0}]", string.Join(", ", Ls(pathList, "aaa/ddd/")));
        Console.WriteLine("[{0}]", string.Join(", ", Ls(pathList, "bbb/")));
        Console.WriteLine("[{0}]", string.Join(", ", Ls(pathList, "bbb/ddd/")));
    }
    static string[] Ls(string[] paths, string pattern) {
        SortedList<string, string> list = new SortedList<string, string>();
        Array.ForEach(paths, delegate(string x) {
            if (x.StartsWith(pattern)) {
                x = x.Substring(pattern.Length);
                int i = x.IndexOf('/');
                list[i < 0 ? x : x.Substring(0, i + 1)] = null;
            }
        });
        return new List<string>(list.Keys).ToArray();
    }
}
Squeak Smalltalk で。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
| ls list |

ls := [:pathList :pathTo |
    | start stream results path |
    start := pathTo size + 1.
    stream := pathList readStream.
    results := OrderedCollection new.
    [(path := stream next) notNil] whileTrue: [
        (path beginsWith: pathTo) ifTrue: [
            | end |
            end := path indexOf: $/ startingAt: start.
            end isZero ifTrue: [end := path size].
            results add: (path copyFrom: start to: end)]].
    results asArray].

list := #('aaa/bbb' 'aaa/ccc' 'aaa/ddd/eee' 'bbb/ddd/eee').

ls value: list value: 'aaa/'.
   "=> #('bbb' 'ccc' 'ddd/') "
ls value: list value: 'aaa/ddd/'.
   "=> #('eee') "

C#3.0で拡張メソッドを使ってみました．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using System;
using System.Linq;
using System.Collections.Generic;

static class Program {
    static string RemoveAfter(this string s, char ch) {
        int index = s.IndexOf(ch);
        return (0 <= index && index < s.Length - 1) ? s.Remove(index + 1) : s;
    }
    static void ls(IEnumerable<string> pathList, string path) {
        if (!path.EndsWith("/")) path += '/';

        var x = from y in pathList where y.StartsWith(path)
                select '"' + y.Substring(path.Length).RemoveAfter('/') + '"';

        Console.WriteLine("[{0}]", string.Join(", ", x.Distinct().ToArray()));
    }
    static void Main(string[] args) {
        string[] pathList = { "aaa/bbb", "aaa/ccc", "aaa/ddd/eee", "bbb/ddd/eee" };

        ls(pathList, "aaa/");
        ls(pathList, "aaa/ddd/");
    }
}

一応ディレクトリツリー作ってみた。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
<?php
function ls($pathlist,$path)
{
    $fs=array();
    $path=trim($path,'/');
    foreach($pathlist as $file)
        eval('$fs[\''.str_replace("/","']['",$file).'\']=1;');
    return eval('return array_keys($fs[\''.str_replace("/","']['",$path).'\']);');
}

$pathList = array("aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee");
print_r(ls($pathList,"aaa/"));
print_r(ls($pathList,"aaa/ddd/"));
?>

あえて木構造とかを作らず、そのまま正規表現で処理してみた。

Dan the Regular Expressionist 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#!/usr/local/bin/perl
use strict;
use warnings;
sub pls{
    my $where = shift;
    my @list  = @_;
    $where =~ s,/?\z,/,o;
    my $pat = qr/\A\Q$where/;
    map { s/$pat//; s,/.*,,; $_ } grep /$pat/, @list;
}

if (__FILE__ eq $0){
    local $\ = "\n";
    local $, = ", ";
    my @pathList = ("aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee");
    print pls("aaa/", @pathList);
    print pls("aaa/ddd", @pathList);
}

Rubyで．真面目にディレクトリツリーを作って処理しています．

ついでに，パスリストへの動的な追加(add)と，基準パス以下の仮想ファイル一覧の出力(lslR)を追加しました．

x = PathList.new("aaa/bbb", "aaa/ccc", "aaa/ddd/eee", "bbb/ddd/eee")
pp x.ls('aaa/')
=> ["bbb", "ccc", "ddd/"]
pp x.ls('aaa/ddd/')
=> ["eee"]

x.add('bbb/foo', 'bbb/bar', 'bbb/baz/hoge')
pp x.ls('bbb')
=> ["ddd/", "baz/", "foo", "bar"]
pp x.ls()
=> ["aaa/", "bbb/"]

pp x.lslR
=> ["aaa/bbb",
    "aaa/ccc",
    "aaa/ddd/eee",
    "bbb/ddd/eee",
    "bbb/baz/hoge",
    "bbb/foo",
    "bbb/bar"]

pp x.lslR('bbb')
=> ["bbb/ddd/eee", "bbb/baz/hoge", "bbb/foo", "bbb/bar"]

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class PathList
  def initialize(*obj)
    @files = Hash.new {|hash, key| hash[key] = PseudoDir.new(key) }
    self.add(*obj) unless obj.empty?
  end

  def add(*obj)
    obj.flatten.each do |path|
      path = path2list(path)
      @files[path[0]] += path[1..-1]
    end
    return self
  end

  def ls(path = '')
    path = path2list(path)
    return lscurdir if path.empty?
    return @files[path[0]].ls(path[1..-1])
  end

  def lslR(path = '')
    path = path2list(path)
    return @files[path[0]].lslR(path[1..-1]) unless path.empty?
    return self.traversal('')
  end

  def lscurdir
    @files.map {|name, file| file.name }
  end

  def traversal(prefix = '')
    @files.map do |name, file|
      file.traversal(prefix + self.name)
    end.flatten
  end

  def path2list(path)
    return path unless path.class == String     # XXX
    path.split(%r|/|)
  end

  def name
    ''
  end
end

class PseudoDir < PathList
  def initialize(name = nil)
    @name = name
    super()
  end

  def +(obj)
    name, rest = obj[0], obj[1..-1]
    return PseudoFile.new(@name) if obj.empty?

    @files[name] += rest
    return self
  end

  def name
    @name + '/'
  end
end

class PseudoFile < PathList
  attr_reader(:name)
  def initialize(name)
    @name = name
  end

  def +(obj)
    raise "#{self.name}: PseudoFile already exists"
  end

  def ls(list = [])
    return [] unless list.empty?  # No such file or directory
    return [self.name]
  end

  def traversal(prefix)
    return prefix + self.name
  end
end
__END__

本筋とは関係ありませんが，lslRの出力が絶対パス(?)となっていたのを，相対パスでの出力となるように修正しました．

pp x.lslR('bbb')
=> ["ddd/eee", "baz/hoge", "foo", "bar"]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
--- pseudo-ls.rb.orig   2007-11-27 21:20:03.000000000 +0900
+++ pseudo-ls.rb        2007-11-27 21:20:16.000000000 +0900
@@ -30,7 +30,7 @@

   def traversal(prefix = '')
     @files.map do |name, file|
-      file.traversal(prefix + self.name)
+      file.traversal(prefix + file.name)
     end.flatten
   end

@@ -79,7 +79,7 @@
   end

   def traversal(prefix)
-    return prefix + self.name
+    return prefix
   end
 end
 __END__

一応，スラッシュを補完。

1
2
3
4
5
6
function l$(lst, dir){
  if(dir.indexOf('/') < 0) dir += '/';
  var r = [], i = 0;
  lst.join('\n').replace(RegExp('^'+ dir +'([^/\n]+/?)', 'mg'), function(_, $){ r[i++] = $ });
  return r;
}

毎回リストを与えるならちゃんと構造作ってもあまり意味ないかな。

1
2
3
4
5
6
7
def ls(plst:List[String], dir:String) = {
  (for(p <- plst if p.startsWith(dir)) yield {
    val a = p.substring(dir.size)
    val i = a.indexOf("/")
    a.substring(0,if(i<0){a.size}else{i+1})
  }) removeDuplicates
}

第一引数の文字列の末尾は "/" ではなく、 第二引数の末尾は "/" であることを仮定しています。

やり方はまあ普通です。リスト生成に mapcan を使ってみました。

1
2
3
4
5
6
7
8
(defun ls (files dir)
  (let ((len (length dir)))
    (mapcan (lambda (f)
              (and (>= (length f) len)
                   (string= f dir :end1 len)
                   (let ((p (position #\/ f :start len)))
                     (list (subseq f len (and p (1+ p)))))))
            files)))

が、ループの方が簡潔に書けました。それと、都合のいい入力を仮定するなら mismatch でよさそう。

1
2
3
4
5
6
(defun ls (files dir)
  (loop with len = (length dir)
    for f in files
    if (= (mismatch f dir) len)
    collect (let ((p (position #\/ f :start len)))
              (subseq f len (and p (1+ p))))))

効率は考えてません。

1
2
3
4
5
6
7
import re

ls = lambda list, dir: [re.findall(dir + '([^/]+/?)', s)[0] for s in list if s.startswith(dir)]

pathList = ["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"]
print ls(pathList, 'aaa/')
print ls(pathList, 'aaa/ddd/')

#4465での指摘への対処。
1
2
3
4
5
6
7
import re

ls = lambda list, dir: dict.fromkeys([re.findall(dir + '([^/]+/?)', s)[0] for s in list if s.startswith(dir)]).keys()

pathList = ["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"]
print ls(pathList, 'aaa/')
print ls(pathList, 'aaa/ddd/')

 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
#!/usr/bin/env gosh

(use gauche.test)
(use srfi-1)

(define path-list (list "aaa/bbb" "aaa/ccc" "aaa/ddd/eee" "bbb/ddd/eee"))

(define (ls path-list dir)
  (define (matcher x)
    (and-let* ((rx (string->regexp #`"^,(regexp-quote dir)/?([^/]+/?)"))
               (m (rx x))
               (r (m 1)))
      r))
  (filter-map matcher path-list))

(test-start "path-list")
(test* "case '(ls path-list \"aaa/\")'"
       '("bbb" "ccc" "ddd/") (ls path-list "aaa/"))
(test* "case '(ls path-list \"aaa/ddd/\")'"
       '("eee") (ls path-list "aaa/ddd/"))
(test* "case '(ls path-list \"aaa/ddd\")'"
       '("eee") (ls path-list "aaa/ddd"))
(test* "case '(ls path-list \"aaa/bbb\")'"
       () (ls path-list "aaa/bbb"))
(test-end)
コメントといえばＣで文字列処理をかくとポインタ演算だらけになるなあ、ということくらいか。
あとリスト処理が面倒・・・。
※リストの最後にNULLターミネータを付加
※結果はstdoutにしちゃいました 
 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
#include <stdio.h>
#include <string.h>

#define PATH_MAX 256
const char *pathList[] = {"aaa/bbb", "aaa/ccc", "aaa/ddd/eee", "bbb/ddd/eee", NULL};

void ls(const char **list, const char *dir){
    char buf[PATH_MAX], *p;
    size_t dirlen = strlen(dir);
    while(*list){
        if(strncmp(*list, dir, dirlen) == 0){
            strcpy(buf, *list + dirlen);
            p = buf;
            while(*p){
                *(p+1) = (*p == '/') ? '\0' : *(p+1);
                p++;
            }
            puts(buf);
        }
        list++;
    }
}

int main(){
    ls(pathList, "aaa/");
    putchar('\n');
    ls(pathList, "aaa/ddd/");
    return 0;
}

sayは、printlnだと思ってください。

1
2
3
4
5
6
//function say(s){WScript.Echo(s);}
var pathList = ["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee" , "aaa"];

ls(pathList,"aaa/");
ls(pathList,"aaa/ddd/");
function ls(x,y){ for( var i in x ) x[i].match('^.*' + y + '([^\\/]+(/|$))') && say(RegExp.$1); }

素朴に。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class Ls {
    public static List<String> ls(String[] pathList, String path) {
        List<String> ret = new ArrayList<String>();
        for (String p : pathList) {
            if (p.startsWith(path)) {
                int n = p.lastIndexOf("/");
                n = n == path.length() - 1 ? p.length() : n + 1;
                ret.add(p.substring(path.length(), n));
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        String[] pathList = new String[] { "aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee" };
        for (String path : ls(pathList, "aaa/")) {
            System.out.println(path);
        }
        for (String path : ls(pathList, "aaa/ddd/")) {
            System.out.println(path);
        }
    }
}

正規表現です。grep に直接ブロックをわたし、Regexp.last_match をつかってみました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def ls(pl, q)
    pl.grep(/^#{Regexp.quote(q)}\/?/) {|x|
        x.sub(Regexp.last_match[0], "").sub(/\/.+/, "/")
    }.delete_if {|i| i.empty? }
end

pathList = ["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"]
p ls(pathList, "aaa/")     == ["bbb", "ccc", "ddd/"]
p ls(pathList, "aaa/ddd/") == ["eee"]
p ls(pathList, "aaa/ddd")  == ["eee"]

とりあえずでLINQを使ってみました。 LINQを使う前提で作ったのが原因では無いと思いますが、可読性の低いコードだなぁ・・・

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class LsClone
{
    static void Main(string[] args)
    {
        string[] pathList = {"aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"};
        Console.WriteLine( ls(pathList, "aaa/") );
        Console.WriteLine(ls(pathList, "aaa/ddd/"));
        Console.WriteLine(ls(pathList, "bbb/ddd/"));
    }

    public static string ls(string[] pathList, string pattern)
    {
        string str = "[";
        var list = from path in pathList where  path.Length> pattern.Length && path.Substring(0, pattern.Length)==pattern
                   select path.Remove(0, pattern.Length).IndexOf('/') == -1 ? path.Remove(0, pattern.Length) : path.Split( new char[]{'/'})[1]+"/";
        foreach (string p in list) str += "\"" + p + "\",";
        return str.Substring(0,str.Length-1) + "]";
    }
}

クロージャで実装してみました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def create(path_list):
    root = {}
    for path in path_list:
        node = root
        for name in path.rstrip("/"