algorithm - コードゴルフ: 複数の並べ替えられたリストを 1 つの並べ替えられたリストに結合する

Question

任意の数のソート済みリストを 1 つのソート済みリストにマージするアルゴリズムを実装します。目的は、好きな言語で最小の作業プログラムを作成することです。

例えば：

input:  ((1, 4, 7), (2, 5, 8), (3, 6, 9))
output: (1, 2, 3, 4, 5, 6, 7, 8, 9)

input:  ((1, 10), (), (2, 5, 6, 7))
output: (1, 2, 5, 6, 7, 10)

注: 入力リストを連結してから言語提供の並べ替え関数を使用するソリューションは、ゴルフの精神に沿わないため、受け入れられません。

sorted(sum(lists,[])) # cheating: out of bounds!

他のものとは別に、アルゴリズムははるかに高速である必要があります (ただし、そうである必要はありません)。

言語、弱点、文字数を明確に述べてください。カウントには意味のある文字のみを含めますが、芸術的/読みやすくするためにコードに空白を自由に追加してください。

物事を整理するために、「改訂」ごとに新しい回答を作成するのではなく、コメントで改善を提案するか、必要に応じて回答を編集してください。

編集: この質問を再度送信する場合は、「ソートを提供する言語なし」ルールを「すべてのリストを連結せずに結果をソートする」ように拡張します。concatenate-then-sort を行う既存のエントリは、実際には非常に興味深くコンパクトであるため、それらが違反するルールをさかのぼって導入することはしませんが、新しい提出物でより制限的な仕様に自由に取り組んでください。

Python でソートされた 2 つのリストを結合することに触発されました

score 19 · Accepted Answer

42 文字の OCaml:

let f=List.fold_left(List.merge compare)[]

正確には42の追加クレジットを取得する必要があると思いますか?

score 8 · Accepted Answer

Python: 113 文字

def m(c,l):
    try:
        c += [l[min((m[0], i) for i,m in enumerate(l) if m)[1]].pop(0)]
        return m(c,l)
    except:
        return c

# called as:
>>> m([], [[1,4], [2,6], [3,5]])
[1, 2, 3, 4, 5, 6]

編集:パフォーマンスの話がいくつかの場所で出てきたので、特にリストが大きくなるにつれて、これはかなり効率的な実装だと思うことを述べます。ソートされた乱数の 10 個のリストに対して 3 つのアルゴリズムを実行しました。

私の解決策（マージ）
sorted(sum(lists, []))(内蔵)
別の方法でソートされたDeestan のソリューション(再実装)

リストマージのパフォーマンス

編集2：（JFS）

図のラベル:

merge_26-- heapq.merge()Python 2.6 stdlib から
merge_alabaster-- 上記のコード (Merge上の図のラベル)
sort_builtin--L = sum(lists,[]); L.sort()
Deestan の解は O(N**2) であるため、比較から除外されます (他のすべての解は O(N) (提供された入力に対して) です)

入力データは[f(N) for _ in range(10)]で、f()は次のとおりです。

max_ = 2**31-1
def f(N):
    L = random.sample(xrange(max_), n)
    L.sort()
    return L
f.__name__ = "sorted_random_%d" % max_

性能データ Nmax=2**16 注:が原因でmerge_alabaster()動作しません。N > 100RuntimeError: "maximum recursion depth exceeded"

この Figure を生成した Python スクリプトを取得するには、次のように入力します。

$ git clone git://gist.github.com/51074.git

結論: かなり大きなリストの場合、組み込みの並べ替えは線形に近い動作を示し、最も高速です。

score 8 · Accepted Answer

Common Lisp には、言語標準の一般的なシーケンス用の関数が既にありますが、merge2 つのシーケンスでしか機能しません。昇順で並べ替えられた複数の数値リストの場合、次の関数で使用できます (必須の 97 文字)。

(defun m (&rest s)
  (if (not (cdr s))
      （車）
      (#'m を適用
             (cons (merge 'list (car s) (cadr s) #'<)
                   (cddr s)))))

編集: しばらくしてから再訪: これは 1 行で実行できます:

(defun multi-merge (&rest lists)
  (reduce (lambda (a b) (merge 'list a b #'<)) lists))

これには、意味のある名前を持つ 79 の必須文字があり、それらを 1 文字に減らすと、61 になります。

(defun m(&rest l)(reduce(lambda(a b)(merge 'list a b #'<))l))

score 7 · Accepted Answer

Ruby: 100 文字 (1 つの重要な空白、4 つの重要な改行)

def m(i)
  a=[]
  i.each{|s|s.each{|n|a.insert((a.index(a.select{|j|j>n}.last)||-1)+1,n)}}
  a.reverse
end

人間バージョン:

def sorted_join(numbers)
  sorted_numbers=[]

  numbers.each do |sub_numbers|
    sub_numbers.each do |number|
      bigger_than_me = sorted_numbers.select { |i| i > number }
      if bigger_than_me.last
        pos = sorted_numbers.index(bigger_than_me.last) + 1
      else
        pos = 0
      end

      sorted_numbers.insert(pos, number)
    end
  end

  sorted_numbers.reverse
end

これはすべて、次のように置き換えることができますnumbers.flatten.sort

ベンチマーク:

 a = [[1, 4, 7], [2, 4, 8], [3, 6, 9]]
 n = 50000
 Benchmark.bm do |b|
   b.report { n.times { m(a) } }
   b.report { n.times { a.flatten.sort } }
 end

プロデュース:

      user     system      total        real
 2.940000   0.380000   3.320000 (  7.573263)
 0.380000   0.000000   0.380000 (  0.892291)

だから、私のアルゴリズムはひどく実行されます。

score 6 · Accepted Answer

再提出した

Python - 74 文字(空白と改行をカウント)

def m(i):
 y=[];x=sum(i,[])
 while x:n=min(x);y+=[n];x.remove(n)
 return y

iリストのリストとして入力されます

使用法：

>>> m([[1,5],[6,3]])
[1, 3, 5, 6]

score 5 · Accepted Answer

Haskell: 127 文字 (インデントと改行なし)

m l|all null l=[]
   |True=x:(m$a++(xs:b))
 where
   n=filter(not.null)l
   (_,min)=minimum$zip(map head n)[0..]
   (a,((x:xs):b))=splitAt min n

基本的に、2 つのリストのマージを一般化します。

score 4 · Accepted Answer

これはここに置いておきます...

言語：C、文字数：265

L[99][99];N;n[99];m[99];i;I;b=0;main(char t){while(scanf("%d%c",L[i]+I,&t)+1){++
I;if(t==10){n[i++]=I;I=0;}}if(I)n[i++] = I;N=i;while(b+1){b=-1;for(i=0;i<N;++i){
I=m[i];if(I-n[i])if(b<0||L[i][I]<L[b][m[b]])b=i;}if(b<0)break;printf("%d ",L[b][
m[b]]);++m[b];}puts("");}

次のように入力します。

1 4 7
2 5 8
3 6 9
(EOF)

score 2 · Accepted Answer

(他のすべての解は O(N) (提供された入力に対して))

出力の要素数を N 、入力リストの数を k とすると、O(N log k) よりも速く実行することはできません。各リストが 1 つの要素のみであり、 O(N log N) よりも高速な比較ベースの並べ替えがあります。

私が見たものは、O(N*k) のように見えます。

かなり簡単に O(N log k) 時間に到達できます: リストをヒープに入れるだけです。これは、I/O 効率の高い並べ替えを行う方法の 1 つです (クイックソートとヒープ/ヒープソートも一般化できます)。

[コードなし、コメントのみ]

score 2 · Accepted Answer

私はこれを試す忍耐がありませんでしたが、私の同僚は、0 文字のキーを使用してこれを行うことができる方法を教えてくれました - Whie Space

score 2 · Accepted Answer

Javascript

function merge(a) {
    var r=[], p;
    while(a.length>0) {
        for (var i=0,j=0; i<a.length && p!=a[j][0]; i++)
            if (a[i][0]<a[j][0])
                j = i;

        r.push(p = a[j].shift());

        if (!a[j].length)
            a.splice(j, 1);
    }
    return r;
}

テスト：

var arr = [[1, 4, 7], [2, 5, 8], [3, 6, 9]];
alert(merge(arr));

score 2 · Accepted Answer

F#: 116 文字:

let p l=
    let f a b=List.filter(a b) in
    let rec s=function[]->[]|x::y->s(f(>)x y)@[x]@s(f(<=)x y) in
    [for a in l->>a]|>s

注: このコードにより、F# は多くの警告をスローしますが、機能します :)

空白と意味のある識別子を含む注釈付きバージョンを次に示します (注: 上記のコードは #light 構文を使用しませんが、以下のコードは使用します)。

let golf l=
    // filters my list with a specified filter operator
    // uses built-in F# function
    // ('a -> 'b -> bool) -> 'a -> ('b list -> 'b list)
    let filter a b = List.filter(a b)

    // quicksort algorithm
    // ('a list -> 'a list)
    let rec qsort =function
        | []->[]
        | x :: y -> qsort ( filter (>) x y) @ [x] @ qsort ( filter (<=) x y)

    // flattens list
    [for a in l ->> a ] |> qsort

score 1 · Accepted Answer

VB は通常、コードゴルフに最適な言語ではありませんが、とにかくここでは使用します。

セットアップ -


        Dim m1 As List(Of Integer) = New List(Of Integer)
        Dim m2 As List(Of Integer) = New List(Of Integer)
        Dim m3 As List(Of Integer) = New List(Of Integer)
        Dim m4 As List(Of Integer) = New List(Of Integer)

        m1.Add(1)
        m1.Add(2)
        m1.Add(3)

        m2.Add(4)
        m2.Add(5)
        m2.Add(6)

        m3.Add(7)
        m3.Add(8)
        m3.Add(9)

        Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
        m5.Add(m1)
        m5.Add(m2)
        m5.Add(m3)

VB.NET での試み (ソートなし)

        While m5.Count > 0
            Dim idx As Integer = 0
            Dim min As Integer = Integer.MaxValue
            For k As Integer = 0 To m5.Count - 1
                If m5(k)(0) < min Then min = m5(k)(0) : idx = k
            Next
            m4.Add(min) : m5(idx).RemoveAt(0)
            If m5(idx).Count = 0 Then m5.RemoveAt(idx)
        End While

別の VB.NET 試行 (許可された並べ替えを使用)


    Private Function Comp(ByVal l1 As List(Of Integer), ByVal l2 As List(Of Integer)) As Integer
        Return l1(0).CompareTo(l2(0))
    End Function
    .
    .
    .
    While m5.Count > 0
        m5.Sort(AddressOf Comp)
        m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
        If m5(0).Count = 0 Then m5.RemoveAt(0)
    End While

プログラム全体 -

        Dim rand As New Random
        Dim m1 As List(Of Integer) = New List(Of Integer)
        Dim m2 As List(Of Integer) = New List(Of Integer)
        Dim m3 As List(Of Integer) = New List(Of Integer)
        Dim m4 As List(Of Integer) = New List(Of Integer)
        Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
        m5.Add(m1)
        m5.Add(m2)
        m5.Add(m3)

        For Each d As List(Of Integer) In m5
            For i As Integer = 0 To 100000
                d.Add(rand.Next())
            Next
            d.Sort()
        Next

        Dim sw As New Stopwatch
        sw.Start()
        While m5.Count > 0
            Dim idx As Integer = 0
            Dim min As Integer = Integer.MaxValue
            For k As Integer = 0 To m5.Count - 1
                If m5(k)(0) < min Then min = m5(k)(0) : idx = k
            Next
            m4.Add(min) : m5(idx).RemoveAt(0)
            If m5(idx).Count = 0 Then m5.RemoveAt(idx)
        End While
        sw.Stop()

        'Dim sw As New Stopwatch
        'sw.Start()
        'While m5.Count > 0
        '    m5.Sort(AddressOf Comp)
        '    m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
        '    If m5(0).Count = 0 Then m5.RemoveAt(0)
        'End While
        'sw.Stop()

        Console.WriteLine(sw.Elapsed)
        Console.ReadLine()

score 1 · Accepted Answer

Perl: 22 文字 (2 つの重要な空白文字を含む)。

sub a{sort map{@$_}@_}

ここではビルトインのみ。見る？;)

次のように呼び出します。

my @sorted = a([1, 2, 3], [5, 6, 89], [13, -1, 3]);
print "@sorted" # prints -1, 1, 1, 2, 3, 3, 5, 6, 89

正直なところ、言語機能 (注: ライブラリではありません...) を否定することは、要点に反するように思えます。言語で実装する最短のコードには、ビルドイン/言語機能を含める必要があります。もちろん、モジュールをインポートする場合は、そのコードをソリューションに対してカウントする必要があります。

編集: $_ の周りの不要な {} を削除しました。

score 1 · Accepted Answer

F#、32 文字

let f x=List.sort(List.concat x)

また、concat (57 文字) に組み込み関数を使用しない場合:

let f x=List.sort(Seq.toList(seq{for l in x do yield!l}))

score 1 · Accepted Answer

C#

static void f(params int[][] b)
{
    var l = new List<int>();
    foreach(var a in b)l.AddRange(a);
    l.OrderBy(i=>i).ToList().ForEach(Console.WriteLine);
}
static void Main()
{
    f(new int[] { 1, 4, 7 },
      new int[] { 2, 5, 8 },
      new int[] { 3, 6, 9 });
}

score 1 · Accepted Answer

ルビー:

41 個の有効な文字、merge メソッドの本体にある 3 つの有効な空白文字。

arrs は配列の配列です


  def merge_sort(arrs)
    o = Array.new
    arrs.each do |a|
      o = o | a
    end
    o.sort!
  end

irb でテストするには:


  arrs = [ [ 90, 4, -2 ], [ 5, 6, -100 ], [ 5, 7, 2 ] ]
  merge_sort(arrs)

戻り値: [-100、-2、2、4、5、6、7、90]

編集:言語提供のマージ/ソートを使用しました。これは、C コードでサポートされている可能性が高く、「より高速」な要件を満たしているためです。後で解決策について考えます (ここは週末で、休暇中です)。

score 0 · Accepted Answer

約250の必須文字でBASH

BASHはリストの操作があまり得意ではありませんが、とにかくこれでうまくいきます。

# This merges two lists together
m(){ 
    [[ -z $1 ]] && echo $2 && return; 
    [[ -z $2 ]] && echo $1 && return; 
    A=($1); B=($2); 
    if (( ${A[0]} > ${B[0]} ));then 
        echo -n ${B[0]}\ ;
        unset B[0];
    else 
        echo -n ${A[0]}\ ;
        unset A[0];
    fi;
    m "${A[*]}" "${B[*]}";
}
# This merges multiple lists
M(){
    A=$1;
    shift;
    for x in $@; do
        A=`m "$A" "$x"`
    done
    echo $A
}

$ M '1 4 7' '2 5 8' '3 6 9'
1 2 3 4 5 6 7 8 9

score 0 · Accepted Answer

ここでは、Pythonに対する@Sykoraの応答よりもはるかに優れているとは思いません。

入力を処理するように変更されました：

import heapq
def m(i): 
    return list(heapq.merge(*i))

print m(((1, 4, 7), (2, 5, 8), (3, 6, 9)))

実際の機能の場合、59文字、または縮小版では52文字：

import heapq
def m(i): return list(heapq.merge(*i))

これには、Pythonに組み込まれたテスト済みの真の実装を使用するという利点もあります。

編集：セミコロンを削除しました（@Douglasに感謝）。

score 0 · Accepted Answer

Python、107文字：

def f(l):  
 n=[]  
 for t in l:  
  for i in t: n+=[t]  
 s=[]  
 while n: s.+=[min(n)]; n.remove(min(n))  
 return s

score 0 · Accepted Answer

ルールに違反するかもしれませんが。これが素晴らしく短いc++エントリです：

13文字

l1.merge(l2); // Removes the elements from the argument list, inserts 
              // them into the target list, and orders the new, combined 
              // set of elements in ascending order or in some other 
              // specified order.

score 0 · Accepted Answer

リンクされたリストを介した C での実装。

http://datastructuresandalgorithmsolutions.blogspot.com/2010/02/chapter-2-basic-abstract-data-types_7147.html

score 0 · Accepted Answer

VB.NET (2008) 185 文字

List(Of List(Of Byte)) を受け入れます

Function s(i)

    s=New List(Of Byte)

    Dim m,c
    Dim N=Nothing

    Do
        m=N
        For Each l In i:
            If l.Count AndAlso(l(0)<m Or m=N)Then m=l(0):c=l

        Next

        If m<>N Then s.Add(m):c.Remove(m)       

    Loop Until m=N

End Function

score -1 · Accepted Answer

Python、181 文字

from heapq import *
def m(l):
 r=[]
 h=[]
 for x in l:
  if x:
   heappush(h, (x[0], x[1:]))
 while h:
  e,f=heappop(h)
  r.append(e)
  if f:
   heappush(h, (f.pop(0),f))
 return r

これは O(NlgM) 時間で実行されます。ここで、N はアイテムの総数、M はリストの数です。

score -1 · Accepted Answer

VB

セットアップ:

Sub Main()
    f(New Int32() {1, 4, 7}, _
      New Int32() {2, 5, 8}, _
      New Int32() {3, 6, 9})
End Sub

出力：

Sub f(ByVal ParamArray b As Int32()())
    Dim l = New List(Of Int32)
    For Each a In b
        l.AddRange(a)
    Next
    For Each a In l.OrderBy(Function(i) i)
        Console.WriteLine(a)
    Next
End Sub

algorithm - コード ゴルフ: 複数の並べ替えられたリストを 1 つの並べ替えられたリストに結合する

26 に答える 26

Javascript

約250の必須文字でBASH

Related

Reference

algorithm - コードゴルフ: 複数の並べ替えられたリストを 1 つの並べ替えられたリストに結合する