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("/").split("/"):
            node = node.setdefault(name, {})
    def ls(path):
        node = root
        for name in path.rstrip("/").split("/"):
            node = node.get(name, None)
            if node is None:
                return []
        return [name + "/" if children else name \
            for name, children in node.iteritems()]
    return ls

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

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

となるコードが多い気がするのだけど
こういうのは気にしなくて良い？
初めての投稿です。

cl-ppcreで正規表現を使ってみたかっただけです。
cl-ppcreが入っていない環境では動作しません。

第二引数は/で終わっていない場合にはnilを返すようにしてます。

1
2
3
4
5
6
7
8
(asdf:oos 'asdf:load-op :cl-ppcre)
(defun ls (pathlist path)
  (let ((res nil))
    (if (cl-ppcre:scan "(.*)/" path) 
    (dolist (i pathlist res)
      (multiple-value-bind (s e) (cl-ppcre:scan  path  i) 
        (if (and s (= s '0) e) 
        (setq res (cons  (subseq i  e) res))))))))

変数宣言以外はC書式（だと思う）の単純な文字列比較です。

パスリスト中のパス指定は終端セパレータを許し、"aaa/bbb"と"aaa/bbb/"は等価として扱っています（空文字列として扱うほうが楽な気もするけど、ファイルパスっぽいし）。 出力時セパレータがつくかどうかは、パスリストの出現順に依存。

重複チェックのスピードがorz

 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
#include <stdio.h>
#include <string.h>

#ifndef MAX_PATH
#define MAX_PATH 256
#endif

static const char PATH_SEPARATOR = '/';

size_t add_separator(char* szPath)
{
    size_t n = strlen(szPath);
    if ((n > 0) &&
        (szPath[n - 1] != PATH_SEPARATOR))
    {
        szPath[n] = PATH_SEPARATOR; n++;
        szPath[n] = '\0';
    }
    return n;
}

void ls(const char** pszList, const char* szPath)
{
    char szParent[MAX_PATH + 1];
    strcpy(szParent, szPath);
    size_t nParent = add_separator(szParent);

    for (int i = 0; pszList[i] != NULL; i++)
    {
        if ((strnicmp(pszList[i], szParent, nParent) != 0) ||
            (pszList[i][nParent] == '\0'))
        {
            continue;
        }

        char szChild[MAX_PATH + 1];
        strcpy(szChild, pszList[i]);
        char* pe = strchr(&(szChild[nParent]), PATH_SEPARATOR);
        if (pe != NULL)
        {
            pe[0] = '\0';
        }
        size_t nChild = strlen(szChild);

        bool bExist = false;
        for (int j = (i - 1); (j >= 0) && (bExist == false); j--)
        {
            bExist = ((strnicmp(pszList[j], szChild, nChild) == 0) &&
                        ((pszList[j][nChild] == PATH_SEPARATOR) ||
                         (pszList[j][nChild] == '\0'          ) )  );
        }
        if (bExist != false)
            continue;

        if (pe != NULL)
        {
            pe[0] = PATH_SEPARATOR;
            pe[1] = '\0';
        }
        fprintf(stdout, "%s\n", &(szChild[nParent]));
    }
}

int main(int argc, char* argv[])
{
    const char* pszList[] = {
        "aaa/bbb", "aaa/ccc", "aaa/ddd/eee", "bbb/ddd/eee", NULL };

    ls(pszList, "aaa/");
    fprintf(stdout, "\r\n");

    ls(pszList, "aaa/ddd/");
    fprintf(stdout, "\r\n");

    return 0;
}

文字列配列中に空文字列が含まれている（"aaa//bbb"等）場合に混乱するのと、単純に'/'で分割して階層構造データを作って検索するものと解答に差異が出そうなので修正。 パスリスト中の"aaa/bbb/"は、空文字列が子にあるものとして処理するようにしました。

引数のパスに空文字列を指定した場合は、ルート要素を列挙。"/"だけの場合、"/aaa"や"/bbb"といった空文字列の子要素を表示します。

 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
#include <stdio.h>
#include <string.h>

#ifndef MAX_PATH
#define MAX_PATH 256
#endif

static const char PATH_SEPARATOR = '/';

void ls(const char** pszList, const char* szPath)
{
    char szParent[MAX_PATH + 1];
    strcpy(szParent, szPath);
    size_t nParent = strlen(szParent);
    if ((nParent > 1) && (szPath[nParent - 1] != PATH_SEPARATOR))
    {
        szParent[nParent] = PATH_SEPARATOR; nParent++;
        szParent[nParent] = '\0';
    }

    for (int i = 0; pszList[i] != NULL; i++)
    {
        if (strnicmp(pszList[i], szPath, nParent) != 0)
            continue;

        char szChild[MAX_PATH + 1];
        strcpy(szChild, pszList[i]);

        char* ps = &(szChild[nParent]);
        char* pe = strchr(ps, PATH_SEPARATOR);
        if (pe != NULL)
            pe[0] = '\0';
        size_t nChild = strlen(szChild);

        bool bExist = false;
        for (int j = (i - 1); (j >= 0) && (bExist == false); j--)
        {
            bExist = ((strnicmp(pszList[j], szChild, nChild) == 0) &&
                      ((pszList[j][nChild] == PATH_SEPARATOR) ||
                       (pszList[j][nChild] == '\0'          )));
        }
        if (bExist != false)
            continue;

        if (pe != NULL)
            fprintf(stdout, "[%s]%c\r\n", ps, PATH_SEPARATOR);
        else
            fprintf(stdout, "[%s]\r\n", ps);
    }
}

int main(int argc, char* argv[])
{
    const char* pszList[] = {
        "aaa/bbb", "aaa/ccc", "aaa/ddd/eee", "bbb/ddd/eee", NULL
    };

    ls(pszList, "aaa/");
    fprintf(stdout, "---\r\n");
    ls(pszList, "aaa/ddd/");
    fprintf(stdout, "---\r\n");

    return 0;
}

こんな感じでどうでしょう。

1
2
3
4
5
6
import Data.List
import Data.Maybe
ls ps p = map k $ mapMaybe (stripPrefix p) ps
k [] = []
k ('/':_) = "/"
k (x:xs) = x:k xs

普通に。

 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
#include <string>
#include <vector>
#include <iostream>
#include <iterator>
#include <sstream>

class Search
{
private:
    std::vector < std::string > & m_vs;
    const std::string & m_p;
public:
    Search(std::vector < std::string > & vs, const std::string & p) : m_vs(vs), m_p(p) {}
    void operator () (const std::string & s)
    {
        if (0 == s.compare(0, m_p.size(), m_p)) {
            std::string tmp = s.substr(m_p.size());
            std::string::size_type st = tmp.find("/");
            m_vs.push_back((std::string::npos != st) ? tmp.substr(0, st + 1) : tmp);
        }
    }
};

void ls(const std::vector < std::string > & path_list, const std::string & path)
{
    std::vector < std::string > vs;
    std::for_each(path_list.begin(), path_list.end(), Search(vs, path));
    std::ostringstream oss;
    copy(vs.begin(), vs.end(), std::ostream_iterator < std::string > (oss, ", "));
    std::cout << oss.str().substr(0, oss.str().size() - 2) << std::endl;
}

/*
int main(void)
{
    std::vector < std::string > path_list;
    path_list.push_back("aaa/bbb");
    path_list.push_back("aaa/ccc");
    path_list.push_back("aaa/ddd/eee");
    path_list.push_back("bbb/ddd/eee");

    ls(path_list, "aaa/");
    ls(path_list, "aaa/ddd/");
}
*/

Digital Mars D Compiler v1.015で動作確認しました。

see: プログラミング言語 D 

 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
import std.stdio;
import std.string;
import std.regexp;

void ls(string[] path_list, string path)
{
    string[]    rslt;
    auto rgxp = RegExp(format("^%s([^/]+/?)", path));
    foreach (i; path_list) {
        if (-1 != rgxp.find(i)) {
            rslt ~= rgxp.match(1);
        }
    }
    string    tmp;
    foreach (i; rslt) {
        tmp ~= format("\"%s\",", i);
    }
    writef("[%s]\n", chop(tmp));
}

/*
void main(char[][] args)
{
    static string[] path_list = ["aaa/bbb", "aaa/ccc", "aaa/ddd/eee", "bbb/ddd/eee"]; 
    ls(path_list, "aaa/");
    ls(path_list, "aaa/ddd/");
}
*/

シェルのPathname expansionに依存しているので、*や[],{}なども使えてしまいますが、別に問題ないですよね?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
myls(){
  local ptn a
  ptn=${1/%\//}/
  shift
  while [[ $# -gt 0 ]]; do
    a=${1#$ptn}
    if [[ $a != $1 ]]; then
      echo -n ${a/%\/*/\/}" "
    fi
    shift
  done
  echo
}

pathList=("aaa/bbb" "aaa/ccc" "aaa/ddd/eee" "bbb/ddd/eee")
myls "aaa/" ${pathList[@]}
myls "aaa/ddd/" ${pathList[@]}

#4465も対処済み。

1
2
3
4
5
6
7
8
fun ls x y =
let
  fun uniq l = foldr (fn (b, a) => b :: List.filter (fn x => x <> b) a) [] l

  val p = y ^ (if String.isSuffix "/" y then "" else "/")
in
  (uniq o map (subst "/.*" "/" o subst p "") o List.filter (String.isPrefix p)) x
end

SQLは文字列操作が苦手だけど、無理してやってみました。おそらくMySQL以外では動きません。他のDBでは関数等を読み替えてください。

インデックスを張ってやれば、件数が増えてもパフォーマンスが期待できるところが強みです。 検索はSQLを使い、文字列の加工などは呼び元の高級言語（CとかJavaとか）で行うというのが王道かと。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
-- パス一覧の作成
create table fs(path char(80) primary key);
insert into fs values("aaa/bbb");
insert into fs values("aaa/ccc");
insert into fs values("aaa/ddd/eee");
insert into fs values("aaa/ddd/fff");
insert into fs values("bbb/ddd/eee");
-- "aaa/" の検索
select distinct substr(
           path, length(dir) + 1,
           case instr(path, "/") when 0 then 80 else (instr(path, "/")) end
       ) ls
  from fs, (select "aaa/" dir) _dir
 where path like concat(dir, "%");
-- "aaa/ddd/" の検索
select distinct substr(
           path, length(dir) + 1,
           case instr(path, "/") when 0 then 80 else (instr(path, "/")) end
       ) ls
  from fs, (select "aaa/ddd/" dir) _dir
 where path like concat(dir, "%");

ふつうに。

erl -noshell -s pls -s init stop
["bbb","ccc","ddd/"]
["eee"]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
-module(pls).
-export([start/0]).

start()->
    PathList=["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"],
    ls(PathList,"aaa/"),
    ls(PathList,"aaa/ddd/").

ls(PathList,Target)->
    erlang:display([addslash(string:tokens(string:substr(X,string:len(Target)+1),"/"))||X<-PathList,string:str(X,Target)=:=1]).

addslash([T,_N|_R])->
    T++"/";
addslash([T]) ->
    T.

ぜんぜんふつうにできてなかったー

PathList=["aaa/bbb/ccc","aaa/bbb/ddd"]
ls(PathList,"aaa/")
>["bbb/","bbb/"] ...orz

以下、重複削除したもの。
1
2
[put(addslash(string:tokens(string:substr(X,string:len(Target)+1),"/")),1)||X<-PathList,string:str(X,Target)=:=1],
erlang:display(get_keys(1)).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def ls( pathList, path ){
   println pathList.findAll{
       it.startsWith(path)
   }.collect{
       (it - path).replaceAll(/\/.*/, "/")
   }.unique()
}


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

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]