5

我一直在使用 ReactiveCocoa 工具，遇到了一个有趣的问题。我可以设想任何数量的丑陋、有状态的解决方案，但我非常有信心有一种优雅、实用的方式，无论出于何种原因，它都不会在我的脑海中实现。也许你能帮上忙！

这里的输入信号是两部分字符串，例如"<letter>,<number>". 所需的排序规则是，对于给定的字母，输入值应按顺序出现在输出中<number>（即A,2不应出现在之前A,1），并且所有字母的<letter>输出不应违反字母顺序。（即，B在出现至少一个以 开头的字符串之前，不应出现以 开头的字符串A。） 除了这些规则所规定的以外，期望事物将按照它们提交到输入的顺序到达输出。

考虑以下代码：

RACSubject* input = [RACSubject subject];

RACSignal* output = [input <SOME CHAIN OF SIGNAL FUNCTIONS>];

[output subscribeNext:^(id x) { NSLog(@"(%@)",x); }];

[input sendNext: @"A,2"]; // Expect no output
[input sendNext: @"B,4"]; // Expect no output
[input sendNext: @"B,2"]; // Expect no output
[input sendNext: @"B,1"]; // Expect no output
[input sendNext: @"A,1"]; // Expect output: (A,1) (A,2) (B,1) (B,2) 
// Note: (A,1) (B,1) (B,2) (A,2) would *not* be right because A,2 appeared on the input before B,1
[input sendNext: @"C,1"]; // Expect output: (C,1)
[input sendNext: @"B,3"]; // Expect output: (B,3) (B,4)
[input sendNext: @"C,3"]; // Expect no output
[input sendNext: @"C,2"]; // Expect output: (C,2) (C,3)

还应该“急切地”产生输出。如果我必须等到输入信号完成才能看到输出，这是没有用的（当然，除非排序规则规定是这种情况，即如果A,1最后出现）

有任何想法吗？

4

2 回答 2

5

以命令式的方式编写它，您可能会使用一些累加器变量，然后循环输入值并根据需要操作累加器。

函数式编程中最接近的并行是扫描（在 ReactiveCocoa 中表示为-scanWithStart:reduce:）。扫描允许您通过流“线程化”状态，并在新输入值到达时使用它。

结果看起来非常类似于命令式累加，除了任何突变都不会逃脱扫描块：

RACSignal *output = [[[[input
    map:^(NSString *combo) {
        NSArray *components = [combo componentsSeparatedByString:@","];
        NSInteger number = [components[1] integerValue];

        return RACTuplePack(components[0], @(number));
    }]
    // We need four state parameters:
    // 1. The letter we're waiting for.
    // 2. The number we're waiting for.
    // 3. Values received that cannot be forwarded until a certain
    //    letter/number.
    // 4. The values to forward at each step.
    scanWithStart:RACTuplePack(@"A", @1, @[], @[]) reduce:^(RACTuple *state, RACTuple *letterAndNumber) {
        NSString *waitingLetter = state[0];
        NSNumber *waitingNumber = state[1];
        NSArray *queuedValues = state[2];

        // Enqueue this value until we're ready to send it (which may or may not
        // occur on this step of the scan).
        queuedValues = [queuedValues arrayByAddingObject:letterAndNumber];

        if ([letterAndNumber.first isEqual:waitingLetter] && [letterAndNumber.second isEqual:waitingNumber]) {
            // Determine the next letter and number.
            waitingLetter = …;
            waitingNumber = @(waitingNumber.integerValue + 1);

            // Sort queuedValues lexically and numerically.
            NSArray *forwardValues = …;

            // We should no longer have any values queued, since we want to
            // forward them all.
            return RACTuplePack(waitingLetter, waitingNumber, @[], forwardValues);
        } else {
            // No values should escape the scan yet. Just pass on our queued
            // values.
            return RACTuplePack(waitingLetter, waitingNumber, queuedValues, @[]);
        }
    }]
    map:^(RACTuple *state) {
        // Convert the array of values into a signal.
        NSArray *forwardValues = state.last;
        return forwardValues.rac_sequence.signal;
    }]
    // Forward values from each inner signal in the correct, sorted order.
    concat];

为简洁起见，我省略了一些排序逻辑，但这很容易用算法的确切细节填写。

于 2013-11-08T19:50:13.463 回答
1

正如问题所说的那样，这是一个有效的输出，当您查看between和(A,1) (A,2) (B,1) (B,2) (C,1) (B,3) (B,4)时，我们会发现我们需要存储每个字母的等待数。(C,1)(B,2)(B,3)

更重要的是，正如问题所说：

除了这些规则所规定的之外，期望事物将按照它们提交到输入的顺序到达输出。

所以在转发了一些值之后，我们可能还有一些排队的值。以问题的输出为例，我们肯定还在等待转发之后(B,4)的到来。(B,3)(C,1)

这是一个代码示例，RAC 部分与 Justin 的几乎相同，而我在注释中强调了不同之处：

另外，我发布了一个完整且可运行的代码示例：http ://d.pr/X59S/9p9bT58U 。

RACSubject *input = [RACSubject subject];
RACSignal *output = [[[[input
    map:^(NSString *combo) {
        NSArray *components = [combo componentsSeparatedByString:@","];
        NSInteger number = [components[1] integerValue];

        return RACTuplePack(components[0], @(number));
    }]

    // !!!: DIFF
    // We need there state parameters:
    // 1. The letters and numbers we're waiting for.
    // 2. Values received that cannot be forwarded until a certain
    //    letter/number.
    // 3. The values to forward at each step.
    scanWithStart:RACTuplePack(@{ @"A": @1 }, @[], @[]) reduce:^id(RACTuple *state, RACTuple *letterAndNumber) {
        __block NSDictionary *waitingLettersAndNumbers = state[0];
        __block NSArray *queuedValues = state[1];

        // Enqueue this value until we're ready to send it (which may or may not
        // occur on this step of the scan).
        queuedValues = [queuedValues arrayByAddingObject:letterAndNumber];
        char letterChar = [letterAndNumber.first characterAtIndex:0];

        // !!!: DIFF
        // (letter + 1, number) may be a valid output after forwarding (letter, number + 1)
        if (
            [[waitingLettersAndNumbers objectForKey:letterAndNumber.first] isEqualToNumber:letterAndNumber.second]
            &&
            (letterChar == 'A' || [[waitingLettersAndNumbers objectForKey:[NSString stringWithFormat:@"%c", letterChar - 1]] integerValue] > [letterAndNumber.second integerValue])
        ) {
            NSMutableDictionary *mutableWaitingLettersAndNumbers = [NSMutableDictionary dictionaryWithDictionary:waitingLettersAndNumbers];

            // Sort queuedValues lexically and numerically.
            queuedValues = ...

            // Determine the next letter and number.
            NSMutableArray *forwardValues = [NSMutableArray array];
            NSMutableArray *remindValues = [NSMutableArray array];
            [queuedValues enumerateObjectsUsingBlock:^(RACTuple *tuple, NSUInteger idx, BOOL *stop) {
                ...
            }];

            queuedValues = [remindValues copy];
            waitingLettersAndNumbers = [mutableWaitingLettersAndNumbers copy];

            // !!!: DIFF
            // After forwarding some values, we may still have some queued values.
            return RACTuplePack(waitingLettersAndNumbers, queuedValues, forwardValues);
        } else {
            // No values should escape the scan yet. Just pass on our queued
            // values.
            return RACTuplePack(waitingLettersAndNumbers, queuedValues, @[]);
        }
    }]
    map:^(RACTuple *state) {
        // Convert the array of values into a signal.
        NSArray *forwardValues = state.last;
        return [forwardValues.rac_sequence signalWithScheduler:[RACScheduler immediateScheduler]];
    }]
    // Forward values from each inner signal in the correct, sorted order.
    concat];
于 2013-11-18T09:21:24.413 回答