计算和排序字符串数组的最佳方法是什么

Question

我试图找到一个好的方法来搜索(计算出现次数),然后以有效的方式对String数组进行排序......这是一种在嵌入式系统中运行良好的方式(32Mb)

示例:我必须计算角色A,B,C等的使用时间,保存后验排序结果...

我可以使用公共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

我的排序方法需要能够回答以下事情:按As的数量排序,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];
    }
}

这将保存您的String(用于搜​​索和显示),并设置一个带有匹配字符数的short数组.(如果内存非常低,并且你知道你的字符串中任何一个字符超过255个,你甚至可以将其更改为一个字节数组.)short只有16个字节,所以数组本身只需64个无论你的字符串有多复杂,所有字节都在一起 如果您每次都要为计算计数而付出性能损失,那么您可以摆脱数组并替换getCount()方法,但是您可能最终会通过频繁使用垃圾收集来节省一次性内存记忆,这是一个很大的表现.:)

现在,使用Comparator定义要搜索的规则.例如,要按字符串中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).

通常情况下,如果你试图变得过于聪明,那么你只需要从有效的解决方案中优化自己.:)