java - 对字符串数组进行计数和排序的最佳方法是什么

Question

我正在尝试寻找是否有一种好的方法来搜索(计算出现次数)然后以有效的方式对字符串数组进行排序...这是一种在嵌入式系统中运行良好的方式 (32Mb)

示例:我必须计算字符 A、B、C 等...的使用次数，保存该结果用于后验排序...

我可以使用 public int count(String searchDomain, char searchValue) 方法进行计数，但是每个字符串都应该包含所有字母，例如:

"This is a test string"
A:1,B:0,C:0,D:0,E:1,I:3,F:0,...
"ACAAGATGCCATTGTCCCCCGGCCTCCTGCTGCTGCTGCTCTCCGGGGCCACGGCCACCGCTGCCCTGCC"
A:7,B:0,C:22,G:18

我的排序方法需要能够回答如下问题:按 A、B 的数量排序 首先按 As 排序，然后按 Bs 对该子域进行排序

这不是作业，这是一个需要在手机上运行的应用程序，我需要这个来提高效率，我目前的实现速度太慢并且占用了太多内存。

Answer 1

我会利用 Java 的(非常高效的)内置排序功能。首先，定义一个简单的类来包含您的字符串及其元数据:

class Item
{
    // Your string. It's public, so you can get it if you want,
    // but also final, so you can't accidentally change it.
    public final String string;

    // An array of counts, where the offset is the alphabetical position
    // of the letter it's counting. (A = 0, B = 1, C=2...)
    private final short[] instanceCounts = new short[32];

    public Item(String string)
    {
        this.string = string;
        for(char c : string.toCharArray())
        {
            // Increment the count for this character
            instanceCounts[(byte)c - 65] ++;
        }
    }

    public int getCount(char c)
    {
        return instanceCounts[(byte)c - 65];
    }
}

这将保存您的字符串(用于搜索和显示)，并设置一个包含匹配字符数的短裤数组。 (如果您真的内存不足并且您知道您的字符串中任何一个字符都超过 255 个，您甚至可以将其更改为一个字节数组。)short 只有 16 个字节，所以无论您的字符串有多复杂，数组本身总共只会占用 64 个字节。如果您宁愿为每次计算计数支付性能损失，您可以摆脱数组并替换 getCount() 方法，但您可能最终会通过消耗频繁收集的垃圾来节省一次性内存内存，这是一个很大的性能损失。 :)

现在，使用比较器定义要搜索的规则。例如，要按字符串中 A 的数量排序:

class CompareByNumberOfA implements Comparator<Item>
{
    public int compare(Item arg0, Item arg1) 
    {
        return arg1.getCount('A') - arg0.getCount('A');
    }
}

最后，将所有项目放入一个数组中，并使用内置的(内存效率高的)数组方法进行排序。例如:

public static void main(String args[])
{
    Item[] items = new Item[5];
    items[0]= new Item("ABC");
    items[1]= new Item("ABCAA");
    items[2]= new Item("ABCAAC");
    items[3]= new Item("ABCAAA");
    items[4]= new Item("ABBABZ");

    // THIS IS THE IMPORTANT PART!
    Arrays.sort(items, new CompareByNumberOfA());

    System.out.println(items[0].string);
    System.out.println(items[1].string);
    System.out.println(items[2].string);
    System.out.println(items[3].string);
    System.out.println(items[4].string);
}

您可以定义一大堆比较器，并按您喜欢的方式使用它们。

关于使用 Java 编码要记住的一件事是不要变得太聪明。编译器在针对他们的平台进行优化方面做得非常好，只要您利用他们可以优化的东西(例如内置 API，包括 Arrays.sort)。

通常，如果您试图变得太聪明，您只会从有效的解决方案中优化自己。 :)