字符串数组只包含字谜？

Question

我接受过关于字谜的练习,看起来很容易让我怀疑我错过了什么.我实施的解决方案是我即将提出的解决方案,我想问你是否可以考虑使用我的解决方案进行任何优化,改变方法或问题.我用Java实现了算法.

现在,练习.作为输入我有一个文本作为输出我应该返回这个文本的每一行是否是每一行的一个字谜.也就是说,输入:

一辆出租车契约最疯狂的小鱼L L
A Cab De Hu Hu Min
A A A A A A A A A A A Mill Mill
Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill

该程序应返回True.输入:

一辆出租车契约最疯狂的小鱼L L
A A De Hu Hu Min L A A A A A A A A A A A A Te Te
Mill Mill
Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill Mill

输出必须为False(当然,因为第二行).

现在,我认为非常简单:

• 我创建了2个HashMap:ref和cur.
• 我解析文本的第一行,填写参考.我只计算字母.
• 对于每一行,我将该行解析为cur并检查cur.equals(ref):如果是,则返回false
• 如果我到达文本的末尾,这意味着每一行都是每一行的一个字谜,所以我返回true.

而且......就是这样.我尝试使用88000行的输入文本,它的工作速度非常快.

任何意见？建议？优化？

非常感谢你的帮助.

Answer 1

另一种选择是:

1. 从字符串中删除您不关心的所有字符(标点符号,空格)
2. 把它做成小写
3. 排序字符串
4. 与参考字符串比较(带.equals)

我怀疑你的方式更快.

编辑:

由于@nibot不同意我甚至暗示这一点,并且我不是一个没有证据来回争辩的人,这里有三个解决方案.

它们的实现非常相似:

1. 将行转换为小写
2. 忽略非字母字符
3. ？
4. 检查结果3.匹配第一行的结果

的？部分是以下之一:

• 做一个HashMap角色计数
• 排序字符
• 制作26-int数组(终极哈希表解决方案,但仅适用于拉丁字母表)

我用它来运行它们:

public static void time(String name, int repetitions, Function function,
        int expectedResult) throws Exception {
    long total = 0;
    for (int i = 0; i < repetitions; i++) {
        System.gc();
        long start = System.currentTimeMillis();
        int result = function.call();
        long end = System.currentTimeMillis();
        if (result != expectedResult) {
            System.out.println("Oops, " + name + " is broken");
            return;
        }
        total += end - start;
    }
    System.out.println("Executution of " + name + " took "
            + (total / repetitions) + " ms on average");
}

我的文件类似于OP发布的文件,但是显着更长,从最后开始大约20行非anagram,以确保算法都能正常工作.

我一直得到这样的结果:

Execution of testWithHashMap took 158 ms on average
Execution of testWithSorting took 76 ms on average
Execution of testWithArray took 56 ms on average

如果出现HashMap以下情况,可以大大改善:

• 有办法制作一个 HashMap<char, int>
• 有一种方法可以指定a中的默认值HashMap以及get-and-increment的方式(因此只有一次查找而不是2次查找)

但是,这些不在标准库中,所以我忽略了它们(就像大多数使用Java的程序员一样).

这个故事的寓意是大O并不是一切.您需要考虑n的开销和大小.在这种情况下,n相当小,并且a的开销HashMap很大.如果线条较长,那可能会发生变化,但不幸的是,我不想找出盈亏平衡点的位置.

如果您仍然不相信我,请考虑GCC 在某些情况下在其C++标准库中使用插入排序.