具有出现次数和排序的字符串列表
List of string with occurrences count and sort
我正在开发一个读取大量字符串数据的 Java 应用程序，如下所示：
1 cat (first read)
2 dog
3 fish
4 dog
5 fish
6 dog
7 dog
8 cat
9 horse
...(last read)
我需要一种方法来保持所有对 [string, occurrences] 从上次阅读到第一次阅读的顺序。
字符串出现次数
马 1（第一次打印）
猫 2
狗 4
鱼 2（最后打印）
实际上我使用了两个列表：
1) List<string> input; 我添加所有数据的地方
在我的例子中：
input.add("cat");
input.add("dog");
input.add("fish");
...
2)List<string> possibilities; 我以这种方式插入一次字符串：
if(possibilities.contains("cat")){
possibilities.remove("cat");
}
possibilities.add("cat");
通过这种方式，我得到了一个包含所有可能性的排序列表。
我是这样用的：
int occurrence;
for(String possible:possibilities){
occurrence = Collections.frequency(input, possible);
System.out.println(possible + " " + occurrence);
}
这个技巧很管用，但是太慢了（我有数百万的输入）...有什么帮助吗？
（英语不是我的第一语言，所以请原谅任何错误。）
使用 Map<String, Integer> 作为 @radoslaw pointed, to keep the insertion sorting use LinkedHashMap and not a TreeMap as described here:
LinkedHashMap keeps the keys in the order they were inserted, while a TreeMap is kept sorted via a Comparator or the natural Comparable ordering of the elements.
假设你有某个数组中的所有字符串，将其命名为 listOfAllStrings，遍历此数组并在你的映射中使用字符串作为 key，如果它不存在，则放入映射，如果存在，将 1 与实际结果相加...
Map<String, Integer> results = new LinkedHashMap<String, Integer>();
for (String s : listOfAllStrings) {
if (results.get(s) != null) {
results.put(s, results.get(s) + 1);
} else {
results.put(s, 1);
}
}
使用 TreeMap，它将按照您的 MyStringComparator compare 指定的键继续排序 class 处理 MyString class 包装 String 添加插入索引，例如这个：
// this better be immutable
class MyString {
private MyString() {}
public static MyString valueOf(String s, Long l) { ... }
private String string;
private Long index;
public hashcode(){ return string.hashcode(); }
public boolean equals() { // return rely on string.equals() }
}
class MyStringComparator implements Comparator<MyString> {
public int compare(MyString s1, MyString s2) {
return -s1.getIndex().compareTo(s2.gtIndex());
}
}
构建地图时通过比较器：
Map<MyString,Integer> map = new TreeMap<>(new MyStringComparator());
然后，在解析您的输入时，执行
Long counter = 0;
while (...) {
MyString item = MyString.valueOf(readString, counter++);
if (map.contains(item)) {
map.put(map.get(item)+1);
} else {
map.put(item,1);
}
}
由于不可变class会出现很多实例化，比较器会和equals不一致，不过应该可以的
免责声明：这是未经测试的代码，只是为了展示我要做什么，当我拿到编译器时，我会回来重新检查它。
这是您问题的完整解决方案，
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class DataDto implements Comparable<DataDto>{
public int count = 0;
public String string;
public long lastSeenTime;
public DataDto(String string) {
this.string = string;
this.lastSeenTime = System.currentTimeMillis();
}
public boolean equals(Object object) {
if(object != null && object instanceof DataDto) {
DataDto temp = (DataDto) object;
if(temp.string != null && temp.string.equals(this.string)) {
return true;
}
}
return false;
}
public int hashcode() {
return string.hashCode();
}
public int compareTo(DataDto o) {
if(o != null) {
return o.lastSeenTime < this.lastSeenTime ? -1 : 1;
}
return 0;
}
public String toString() {
return this.string + " : " + this.count;
}
public static final void main(String[] args) {
String[] listOfAllStrings = {"horse", "cat", "dog", "fish", "cat", "fish", "dog", "cat", "horse", "fish"};
Map<String, DataDto> results = new HashMap<String, DataDto>();
for (String s : listOfAllStrings) {
DataDto dataDto = results.get(s);
if(dataDto != null) {
dataDto.count = dataDto.count + 1;
dataDto.lastSeenTime = System.nanoTime();
} else {
dataDto = new DataDto(s);
results.put(s, dataDto);
}
}
List<DataDto> finalResults = new ArrayList<DataDto>(results.values());
System.out.println(finalResults);
Collections.sort(finalResults);
System.out.println(finalResults);
}
}
答案
[horse : 1, cat : 2, fish : 2, dog : 1]
[fish : 2, horse : 1, cat : 2, dog : 1]
我认为这个解决方案将适合您的要求。
如果您知道将数据全部读入内存时不会超出内存容量，那么解决方案很简单——使用一个 LinkedList 或一个和一个 LinkedHashMap。
例如，如果您使用链表：
LinkedList<String> input = new LinkedList();
然后您可以像最初一样继续使用 input.add()。但是当输入列表已满时，您基本上可以使用 Jordi Castilla 的解决方案——但将条目以 倒序 的方式放入链表中。为此，您需要：
Iterator<String> iter = list.descendingIterator();
LinkedHashMap<String,Integer> map = new LinkedHashMap<>();
while (iter.hasNext()) {
String s = iter.next();
if ( map.containsKey(s)) {
map.put( s, map.get(s) + 1);
} else {
map.put(s, 1);
}
}
现在，他的解决方案和我的解决方案之间唯一真正的区别是我使用的是 list.descendingIterator()，这是 LinkedList 中的一种方法，它为您提供倒序的条目，从 [=61] =] 到 "cat".
LinkedHashMap 将保持正确的顺序 - 先输入的内容将首先打印，并且因为我们输入的内容是相反的顺序，所以最后读取的内容将首先打印。因此，如果您打印 map，结果将是：
{horse=1, cat=2, dog=4, fish=2}
如果文件很长，并且无法将整个字符串列表加载到内存中，则最好只保留频率图。在这种情况下，为了保持条目顺序，我们将使用这样的对象：
private static class Entry implements Comparable<Entry> {
private static long nextOrder = Long.MIN_VALUE;
private String str;
private int frequency = 1;
private long order = nextOrder++;
public Entry(String str) {
this.str = str;
}
public String getString() {
return str;
}
public int getFrequency() {
return frequency;
}
public void updateEntry() {
frequency++;
order = nextOrder++;
}
@Override
public int compareTo(Entry e) {
if ( order > e.order )
return -1;
if ( order < e.order )
return 1;
return 0;
}
@Override
public String toString() {
return String.format( "%s: %d", str, frequency );
}
}
这里的诀窍是每次更新条目（频率加一）时，它也会更新顺序。但是 compareTo() 方法将 Entry 对象从 high 顺序（updated/inserted 之后）排序到 low 顺序（ updated/inserted 较早）。
现在您可以使用简单的 HashMap<String,Entry> 来存储您阅读的信息（我假设您是通过某种扫描仪阅读的）：
Map<String,Entry> m = new HashMap<>();
while ( scanner.hasNextLine() ) {
String str = scanner.nextLine();
Entry entry = m.get(str);
if ( entry == null ) {
entry = new Entry(str);
m.put(str, entry);
} else {
entry.updateEntry();
}
}
Scanner.close();
现在您可以对条目的值进行排序：
List<Entry> orderedList = new ArrayList<Entry>(m.values());
m = null;
Collections.sort(orderedList);
运行 System.out.println(orderedList) 会给你：
[horse: 1, cat: 2, dog: 4, fish: 2]
原则上，您可以使用 TreeMap，其键包含 "order" 内容，而不是像这样的普通 HashMap 然后进行排序，但我更喜欢没有任何可变的地图中的键，也不会不断更改键。在这里，我们只在填充地图时更改 值 ，并且每个键仅插入地图一次。
你可以做什么：
- 反转列表的顺序使用
Collections.reverse(input)。这在线性时间内运行 - O(n);
- 从输入列表中创建一个 Set。 Set 保证唯一性。
要保留插入顺序，您需要 LinkedHashSet;
- 像上面那样迭代这个集合。
代码：
/* I don't know what logic you use to create the input list,
* so I'm using your input example. */
List<String> input = Arrays.asList("cat", "dog", "fish", "dog",
"fish", "dog", "dog", "cat", "horse");
/* by the way, this changes the input list!
* Copy it in case you need to preserve the original input. */
Collections.reverse(input);
Set<String> possibilities = new LinkedHashSet<String>(strings);
for (String s : possibilities) {
System.out.println(s + " " + Collections.frequency(strings, s));
}
输出：
horse 1
cat 2
dog 4
fish 2
我正在开发一个读取大量字符串数据的 Java 应用程序，如下所示：
1 cat (first read)
2 dog
3 fish
4 dog
5 fish
6 dog
7 dog
8 cat
9 horse
...(last read)
我需要一种方法来保持所有对 [string, occurrences] 从上次阅读到第一次阅读的顺序。
字符串出现次数
马 1（第一次打印）
猫 2
狗 4
鱼 2（最后打印）
实际上我使用了两个列表：
1) List<string> input; 我添加所有数据的地方
在我的例子中：
input.add("cat");
input.add("dog");
input.add("fish");
...
2)List<string> possibilities; 我以这种方式插入一次字符串：
if(possibilities.contains("cat")){
possibilities.remove("cat");
}
possibilities.add("cat");
通过这种方式，我得到了一个包含所有可能性的排序列表。 我是这样用的：
int occurrence;
for(String possible:possibilities){
occurrence = Collections.frequency(input, possible);
System.out.println(possible + " " + occurrence);
}
这个技巧很管用，但是太慢了（我有数百万的输入）...有什么帮助吗？
（英语不是我的第一语言，所以请原谅任何错误。）
使用 Map<String, Integer> 作为 @radoslaw pointed, to keep the insertion sorting use LinkedHashMap and not a TreeMap as described here:
LinkedHashMapkeeps the keys in the order they were inserted, while aTreeMapis kept sorted via a Comparator or the natural Comparable ordering of the elements.
假设你有某个数组中的所有字符串，将其命名为 listOfAllStrings，遍历此数组并在你的映射中使用字符串作为 key，如果它不存在，则放入映射，如果存在，将 1 与实际结果相加...
Map<String, Integer> results = new LinkedHashMap<String, Integer>();
for (String s : listOfAllStrings) {
if (results.get(s) != null) {
results.put(s, results.get(s) + 1);
} else {
results.put(s, 1);
}
}
使用 TreeMap，它将按照您的 MyStringComparator compare 指定的键继续排序 class 处理 MyString class 包装 String 添加插入索引，例如这个：
// this better be immutable
class MyString {
private MyString() {}
public static MyString valueOf(String s, Long l) { ... }
private String string;
private Long index;
public hashcode(){ return string.hashcode(); }
public boolean equals() { // return rely on string.equals() }
}
class MyStringComparator implements Comparator<MyString> {
public int compare(MyString s1, MyString s2) {
return -s1.getIndex().compareTo(s2.gtIndex());
}
}
构建地图时通过比较器：
Map<MyString,Integer> map = new TreeMap<>(new MyStringComparator());
然后，在解析您的输入时，执行
Long counter = 0;
while (...) {
MyString item = MyString.valueOf(readString, counter++);
if (map.contains(item)) {
map.put(map.get(item)+1);
} else {
map.put(item,1);
}
}
由于不可变class会出现很多实例化，比较器会和equals不一致，不过应该可以的
免责声明：这是未经测试的代码，只是为了展示我要做什么，当我拿到编译器时，我会回来重新检查它。
这是您问题的完整解决方案，
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class DataDto implements Comparable<DataDto>{
public int count = 0;
public String string;
public long lastSeenTime;
public DataDto(String string) {
this.string = string;
this.lastSeenTime = System.currentTimeMillis();
}
public boolean equals(Object object) {
if(object != null && object instanceof DataDto) {
DataDto temp = (DataDto) object;
if(temp.string != null && temp.string.equals(this.string)) {
return true;
}
}
return false;
}
public int hashcode() {
return string.hashCode();
}
public int compareTo(DataDto o) {
if(o != null) {
return o.lastSeenTime < this.lastSeenTime ? -1 : 1;
}
return 0;
}
public String toString() {
return this.string + " : " + this.count;
}
public static final void main(String[] args) {
String[] listOfAllStrings = {"horse", "cat", "dog", "fish", "cat", "fish", "dog", "cat", "horse", "fish"};
Map<String, DataDto> results = new HashMap<String, DataDto>();
for (String s : listOfAllStrings) {
DataDto dataDto = results.get(s);
if(dataDto != null) {
dataDto.count = dataDto.count + 1;
dataDto.lastSeenTime = System.nanoTime();
} else {
dataDto = new DataDto(s);
results.put(s, dataDto);
}
}
List<DataDto> finalResults = new ArrayList<DataDto>(results.values());
System.out.println(finalResults);
Collections.sort(finalResults);
System.out.println(finalResults);
}
}
答案
[horse : 1, cat : 2, fish : 2, dog : 1]
[fish : 2, horse : 1, cat : 2, dog : 1]
我认为这个解决方案将适合您的要求。
如果您知道将数据全部读入内存时不会超出内存容量，那么解决方案很简单——使用一个 LinkedList 或一个和一个 LinkedHashMap。
例如，如果您使用链表：
LinkedList<String> input = new LinkedList();
然后您可以像最初一样继续使用 input.add()。但是当输入列表已满时，您基本上可以使用 Jordi Castilla 的解决方案——但将条目以 倒序 的方式放入链表中。为此，您需要：
Iterator<String> iter = list.descendingIterator();
LinkedHashMap<String,Integer> map = new LinkedHashMap<>();
while (iter.hasNext()) {
String s = iter.next();
if ( map.containsKey(s)) {
map.put( s, map.get(s) + 1);
} else {
map.put(s, 1);
}
}
现在，他的解决方案和我的解决方案之间唯一真正的区别是我使用的是 list.descendingIterator()，这是 LinkedList 中的一种方法，它为您提供倒序的条目，从 [=61] =] 到 "cat".
LinkedHashMap 将保持正确的顺序 - 先输入的内容将首先打印，并且因为我们输入的内容是相反的顺序，所以最后读取的内容将首先打印。因此，如果您打印 map，结果将是：
{horse=1, cat=2, dog=4, fish=2}
如果文件很长，并且无法将整个字符串列表加载到内存中，则最好只保留频率图。在这种情况下，为了保持条目顺序，我们将使用这样的对象：
private static class Entry implements Comparable<Entry> {
private static long nextOrder = Long.MIN_VALUE;
private String str;
private int frequency = 1;
private long order = nextOrder++;
public Entry(String str) {
this.str = str;
}
public String getString() {
return str;
}
public int getFrequency() {
return frequency;
}
public void updateEntry() {
frequency++;
order = nextOrder++;
}
@Override
public int compareTo(Entry e) {
if ( order > e.order )
return -1;
if ( order < e.order )
return 1;
return 0;
}
@Override
public String toString() {
return String.format( "%s: %d", str, frequency );
}
}
这里的诀窍是每次更新条目（频率加一）时，它也会更新顺序。但是 compareTo() 方法将 Entry 对象从 high 顺序（updated/inserted 之后）排序到 low 顺序（ updated/inserted 较早）。
现在您可以使用简单的 HashMap<String,Entry> 来存储您阅读的信息（我假设您是通过某种扫描仪阅读的）：
Map<String,Entry> m = new HashMap<>();
while ( scanner.hasNextLine() ) {
String str = scanner.nextLine();
Entry entry = m.get(str);
if ( entry == null ) {
entry = new Entry(str);
m.put(str, entry);
} else {
entry.updateEntry();
}
}
Scanner.close();
现在您可以对条目的值进行排序：
List<Entry> orderedList = new ArrayList<Entry>(m.values());
m = null;
Collections.sort(orderedList);
运行 System.out.println(orderedList) 会给你：
[horse: 1, cat: 2, dog: 4, fish: 2]
原则上，您可以使用 TreeMap，其键包含 "order" 内容，而不是像这样的普通 HashMap 然后进行排序，但我更喜欢没有任何可变的地图中的键，也不会不断更改键。在这里，我们只在填充地图时更改 值 ，并且每个键仅插入地图一次。
你可以做什么：
- 反转列表的顺序使用 Collections.reverse(input)。这在线性时间内运行 - O(n);
- 从输入列表中创建一个 Set。 Set 保证唯一性。 要保留插入顺序，您需要 LinkedHashSet;
- 像上面那样迭代这个集合。
代码：
/* I don't know what logic you use to create the input list,
* so I'm using your input example. */
List<String> input = Arrays.asList("cat", "dog", "fish", "dog",
"fish", "dog", "dog", "cat", "horse");
/* by the way, this changes the input list!
* Copy it in case you need to preserve the original input. */
Collections.reverse(input);
Set<String> possibilities = new LinkedHashSet<String>(strings);
for (String s : possibilities) {
System.out.println(s + " " + Collections.frequency(strings, s));
}
输出：
horse 1
cat 2
dog 4
fish 2