std.algorithm 算法--1（2.030）

6.1  20 点 更新   
5.21 19点 更新     
5.6  0点 更新   
5.2 18点 更新   
5.1 23点 更新


std.algorithm
Jump to: map reduce fill filter move moveAll moveSome swap Splitter splitter Uniq uniq find BoyerMooreFinder boyerMooreFinder startsWith endsWith findAdjacent findAmong findAmongSorted count equal min max minCount mismatch EditOp none substitute insert remove levenshteinDistance levenshteinDistanceAndPath copy swapRanges reverse bringToFront SwapStrategy unstable semistable stable partition isPartitioned topN sort schwartzSort partialSort completeSort isSorted makeIndex lowerBound upperBound equalRange canFindSorted BinaryHeap acquire release top pop replaceTop length topNCopy SetUnion setUnion SetIntersection setIntersection SetDifference setDifference

    Implements algorithms oriented mainly towards processing of sequences. Some functions are semantic equivalents or supersets of those found in the <algorithm> header in Alexander Stepanov's Standard Template Library for C++.
    算法实现主要面向过程处理。 一些函数語意相同的或者超集（supersets）是在 Alexander Stepanov 的 C++ Standard Template Library 的 < algorithm > 头文件中找到的。

作者:
Andrei Alexandrescu

Note:
    Many functions in this module are parameterized with a function or a predicate . The predicate may be passed either as a function name, a delegate name, a functor name, or a compile-time string. The string may consist of any legal D expression that uses the symbol a (for unary functions) or the symbols a and b (for binary functions). These names will NOT interfere with other homonym symbols in user code because they are evaluated in a different context. The default for all binary comparison predicates is "a == b" for unordered operations and "a < b" for ordered operations.

注意：
    許多模块（module）中的函数是 参数化的函数 或者 断言（predicate）。 断言 可以作為一種函数名、一個委托名、函子（functor）名，或者编译时字符串被傳遞。字符串可以包括任何合法的D符号表达式 a (一元函数)或者符號 a 和 b (二元函数)。 因為他們在一個不同的上下文中被赋值，這些名稱將不干擾其它使用者代碼中的同音異義詞符號。 所有二元的比較 断言“a == b”和 ”a < b” 是預設的指令操作。

Example：

int[] a = ...;
static bool greater(int a, int b)
{
    return a > b;
}
sort!(greater)(a);  // predicate as alias   别名断言
sort!("a > b")(a);  // predicate as string  字符串断言
                    // (没有歧义的数组名)
sort(a);            //沒有断言（predicate），“a < b”是隐式的（implicit）


==========================================================================
5.2 18点 更新

template map(fun...)

Implements the homonym function (also known as transform) present in many languages of functional flavor. The call map!(fun)(range) returns a range of which elements are obtained by applying fun(x) left to right for all x in range. The original ranges are not changed. Evaluation is done lazily. The range returned by map caches the last value such that evaluating front multiple times does not result in multiple calls to fun.
实现异质（homonym）函数(也被稱之為变换)是许多函数语言的风格。调用map!(fun)(range) 返回一个 range ，其中的元素是通过fun(x) 从左到右从 range 中得到的。原來的range没有改變。 由 lazily 完成赋值。 对 map caches最後的值多次赋值不会導致对 fun 的多次调用。

例子:
int[] arr1 = [ 1, 2, 3, 4 ];
int[] arr2 = [ 5, 6 ];
auto squares = map!("a * a")(chain(arr1, arr2));
assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ]));

    Multiple functions can be passed to map. In that case, the element type of map is a tuple containing one element for each function.
    多重的函数能被传递到  map 。 那樣的話，元素类型  map 是每个函数的元组包含一个元素。

例子:
auto arr1 = [ 1, 2, 3, 4 ];
foreach (e; map!("a + a", "a * a")(arr1))
{
    writeln(e.field[0], " ", e.field[1]);
}



template reduce(fun...)

    Implements the homonym function (also known as accumulate, compress, inject, or foldl) present in various programming languages of functional flavor. The call reduce!(fun)(seed, range) first assigns seed to an internal variable result, also called the accumulator. Then, for each element x in range, result = fun(result, x) gets evaluated. Finally, result is returned. The one-argument version reduce!(fun)(range) works similarly, but it uses the first element of the range as the seed (the range must be non-empty).
    实现异质（homonym）函数(也被稱之為累積，壓縮，注入，或者foldl ？)是许多函数语言的风格。调用reduce!(fun)(seed, range) 首先分配一个内部变量（seed 参数），也称之为 累加器 。那么，在 range 中遍历元素 x ，result = fun(result, x) ，最后，返回 result 。一個爭論版本，reduce！(fun)(range)works同樣地工作，但是它（默认）使用 range 的第一個元素作為 seed参数( range 必须是非空的)。

    Many aggregate range operations turn out to be solved with reduce quickly and easily. The example below illustrates reduce's remarkable power and flexibility.
    許多聚合 range 操作終究是解決 reduce 的性能和简单。下面的例子说明 reduce 的非凡能力和灵活性

Example:
int[] arr = [ 1, 2, 3, 4, 5 ];
// Sum all elements  所有元素求和
auto sum = reduce!("a + b")(0, arr);
assert(sum == 15);

// Compute the maximum of all elements  计算最大值
auto largest = reduce!(max)(arr);
assert(largest == 5);

// Compute the number of odd elements 计算奇数数量
auto odds = reduce!("a + (b & 1)")(0, arr);
assert(odds == 3);

// Compute the sum of squares  求平方和
auto ssquares = reduce!("a + b * b")(0, arr);
assert(ssquares == 55);

// Chain multiple ranges into seed  链接多个范围（到种子）

int[] a = [ 3, 4 ];
int[] b = [ 100 ];
auto r = reduce!("a + b")(chain(a, b));
assert(r == 107);

// Mixing convertible types is fair game, too  混合可改变的类型
double[] c = [ 2.5, 3.0 ];
auto r1 = reduce!("a + b")(chain(a, b, c));
assert(r1 == 112.5);

=================================================================
5.6 0点 更新

Multiple functions: 并联函数:

    Sometimes it is very useful to compute multiple aggregates in one pass. One advantage is that the computation is faster because the looping overhead is shared. That's why reduce accepts multiple functions. If two or more functions are passed, reduce returns a std.typecons.Tuple object with one member per passed-in function. The number of seeds must be correspondingly increased.
    有时在计算多个集合时非常有用。 一種優點是因為总开销是共用的，这就是为什么 reduce 接受并联函数。 如果兩或者更多函数被传递, reduce返回一个 std.typecons.tuple 通过每一个成员函数。 种子的数目（seed 参数 ？）必须相应增加。


例子:
Example:
double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
// Compute minimum and maximum in one pass
auto r = reduce!(min, max)(a);
// The type of r is Tuple!(double, double)
assert(r.field[0] == 2);  // minimum
assert(r.field[1] == 11); // maximum

// Compute sum and sum of squares in one pass 求和 和 求平方和
r = reduce!("a + b", "a + b * b")(0.0, 0.0, a);
assert(r.field[0] == 35);  // sum
assert(r.field[1] == 233); // sum of squares求平方和
// Compute average and standard deviation from the above
//求平均数和标准差

auto avg = r.field[0] / a.length;
auto stdev = sqrt(r.field[1] / a.length - avg * avg);


void fill(Range, Value)(Range range, Value filler);

Fills a range with a value. ;用值填充 range 。

Example:
int[] a = [ 1, 2, 3, 4 ];
fill(a, 5);
assert(a == [ 5, 5, 5, 5 ]);


void fill(Range1, Range2)(Range1 range, Range2 filler);

    Fills range with a pattern copied from filler. The length of range does not have to be a multiple of the length of filler. If filler is empty, an exception is thrown.
    用填充器的复制模式填充 range 。 Range 的长度不应该是一个有多种长度的填充器（range 类型）。如果填充器为空，将抛出异常。

Example:
int[] a = [ 1, 2, 3, 4, 5 ];
int[] b = [ 8, 9 ];
fill(a, b);
assert(a == [ 8, 9, 8, 9, 8 ]);


Filter!(unaryFun!(pred),Range) filter(alias pred, Range)(Range rs);

    Implements the homonym function present in various programming languages of functional flavor. The call filter!(fun)(range) returns a new range only containing elements x in r for which pred(x) is true.
    实现异质函数是各种不同的编程语言的函数风格。如果pred( x )为ture，
调用filter！(fun)(range) 返回一個僅包含元素x的新 range 。

Example:
int[] arr = [ 1, 2, 3, 4, 5 ];
// Sum all elements  求元素和
auto small = filter!("a < 3")(arr);
assert(small == [ 1, 2 ]);
// In combination with chain() to span multiple ranges
//在联合（combination）中用 chain() 函数来跨越多个 range 。
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = filter!("a > 0")(chain(a, b));
assert(equals(r, [ 3, 400, 100, 102 ]));
// Mixing convertible types is fair game, too
//混合转换类型
double[] c = [ 2.5, 3.0 ];http://www.windowslivetranslator.com/Default.aspx
auto r1 = filter!("cast(int) a != a")(chain(c, a, b));
assert(r1 == [ 2.5 ]);

=================================================
5.21.2009  19点 更新

void move(T)(ref T source, ref T target);

    Moves source into target via a destructive copy. Specifically:
    透過一個破壞性的拷貝把source 搬動到 target 中。 特别是:
•    If hasAliasing!T is true (see std.traits.hasAliasing), then the representation of source is bitwise copied into target and then source = T.init is evaluated.
     如果hasAliasing!T为 true (参见 std.traits.hasAliasing), 那麼source 将逐位 複製到target ，而且 source = T.init 被赋值。

•    Otherwise, target = source is evaluated.
     否則，target = source 被赋值。

參見std.contracts.pointsTo.

Preconditions: 前提:
!pointsTo(source, source)


Range2 moveAll(Range1, Range2)(Range1 src, Range2 tgt);

    For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Returns the leftover portion of tgt. Throws an exeption if there is not enough room in tgt to acommodate all of src.
    调用 move( a, b)，对于src的每一元素 a 以及tgt的每一元素 b 都将同步递增次序。返回剩余部分的 tgt 。如果 tgt 没有足够的空间来容纳( accommodate ) src 的所有元素将抛出异常。


Preconditions: 前提:
walkLength(src) >= walkLength(tgt)   //   walkLength 步长

Tuple!(Range1,Range2) moveSome(Range1, Range2)(Range1 src, Range2 tgt);

    For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Stops when either src or tgt have been exhausted. Returns the leftover portion of the two ranges.
    调用 move( a, b)，对于src的每一元素 a 以及tgt的每一元素 b 都将同步递增次序。返回剩余部分的 tgt 。。 當src或者tgt耗盡時停止。 返回兩個 range 的剩余部份。

void swap(T)(ref T lhs, ref T rhs);

Swaps lhs and rhs.   交換 lhs 和 rhs 。

參見 std.contracts.pointsTo


Preconditions:  前提:
!pointsTo(lhs，lhs ) &&！pointsTo(lhs，rhs ) &&！pointsTo(rhs，lhs ) &&！pointsTo(rhs，rhs )


struct Splitter(Range,Separator);
Splitter!(Range,Separator) splitter(Range, Separator)(Range r, Separator s);

    Splits a range using another range or an element as a separator. This can be used with any range type, but is most popular with string types.
    使用另一個 range 或者一個元素作為隔符號分隔一個 range 。 這可以用于任何 range 类型，但是最流行的是字符串类型。

Example:
int[ ] a = [ 1, 2, 0, 3, 0, 4, 5, 0 ];
int[ ][ ] w = [ [1, 2], [3], [4, 5] ];
uint i;
foreach (e; splitter(a)) assert(e == w[i++]);
assert(i == 3);


struct Uniq(alias pred,R);
Uniq!(pred,Range) uniq(alias pred = "a == b", Range)(Range r);

    Iterates unique consecutive elements of the given range (functionality akin to the uniq system utility). Equivalence of elements is assessed by using the predicate pred, by default "a == b". If the given range is bidirectional, uniq also yields a bidirectional range.
    对给定的 range 连续迭代其中的元素( 類似于 uniq 函数的 系統工具 )。 元素的相等被断言預設“a == b”。 如果给定的 range 是双向的，uniq也生產一個双向的 range 。

Example:
int[ ] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][ ]));

============================================================

6.1.2009


FindResult!(Range,Ranges) find(alias pred = "a == b", Range, Ranges...)(Range haystack, Ranges needles);

struct BoyerMooreFinder(alias pred,Range);
BoyerMooreFinder!(binaryFun!(pred),Range) boyerMooreFinder(alias pred = "a == b", Range)(Range needle);

    Generalized routine for finding one or more needles into a haystack. Some or all of haystack and needles may be structured in various ways, which translates in the speed of find. The predicate pred is used throughout to compare elements. By default, elements are compared for equality.
    在 Haystack 里发现一个或更多的 needles 。部分或全部 haystack 和 needles 是以不同的方式构造的，找到后被快速的转换。 断言（predicate）在整個元素比較中被使用。 默认情况下，元素是做相等比较

Parameters: 參數:

    haystack ：
    The target of the search. Must be an input range . If any of needles is a range with elements comparable to elements in haystack, then haystack must be a forward range such that the search can backtrack.
    haystack ：
    搜索的目標。 必须是一个 input range . 如果任何 needles 在haystack 中是帶有可以與元素相比较的元素的一個 range ，那麼haystack肯定是一個forward range  這樣搜索能回溯。

    needles：
    One or more items to search for. Each of needles must be either comparable to one element in haystack, or be itself a forward range with elements comparable with elements in haystack.
    needles：
    搜索一个或多个的items。 每个 needles 必须是 haystack 的组成部分，或者本身就是一种在 haystack 中元素与元素是可比较的   forward range 。


Returns: 返回:
    • If needles.length == 1, returns haystack advanced such that needles[0] is a prefix of it (if no such position exists, returns an empty range).
        如果 needles.length == 1,返回 haystack这种先进的 needles[ 0 ]它是首位置的(如果没有這樣的位置存在，返回一個空的 range )。

    • If needles.length > 1, returns a tuple containing haystack positioned as above and also the 1-based index of the matching element in needles (0 if none of needles matched, 1 if needles[0] matched, 2 if needles[1] matched...).
       如果 needles.length > 1，返回包含 haystack 位置的一元組以及 needles中的相匹配的元素1 作為基礎索引( 0  沒有相匹配的 needles，1和needles[0 ]相匹配，2和 needles[ 1 ] 相匹配。..)
======================================================







2.032新增
void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = SortOutput.no);
    Similar to largestPartialIntersection, but associates a weight with each distinct element in the intersection.

    Example:

    // Figure which number can be found in most arrays of the set of
    // arrays below, with specific per-element weights
    double[][] a =
    [
        [ 1, 4, 7, 8 ],
        [ 1, 7 ],
        [ 1, 7, 8],
        [ 4 ],
        [ 7 ],
    ];
    auto b = new Tuple!(double, uint)[1];
    double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ];
    largestPartialIntersectionWeighted(a, b, weights);
    // First member is the item, second is the occurrence count
    assert(b[0] == tuple(4.0, 2u));

    The correct answer in this case is 4.0, which, although only appears two times, has a total weight 4.6 (three times its weight 2.3). The value 7 is weighted with 1.1 and occurs four times for a total weight 4.4.