ما هي بنية البيانات التي ستستخدمها:TreeMap أو HashMap؟(جافا)
https://stackoverflow.com/questions/302371
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
الوصف | برنامج Java لقراءة ملف نصي وطباعة كل كلمة من الكلمات الفريدة بالترتيب الأبجدي مع عدد مرات ظهور الكلمة في النص.
يجب أن يعلن البرنامج عن متغير من النوع Map<String, Integer> لتخزين الكلمات وتكرار حدوثها.أي نوع من الخرسانة، رغم ذلك؟ TreeMap<String, Number> أو HashMap<String, Number> ?
يجب تحويل الإدخال إلى أحرف صغيرة.
الكلمة لا تحتوي على أي من هذه الأحرف: \t\t\n]f.,!?:;\"()'
إخراج المثال |
Word Frequency
a 1
and 5
appearances 1
as 1
.
.
.
ملاحظة | أعلم أنني رأيت حلولاً رائعة لهذا في لغة Perl تحتوي على سطرين تقريبًا من التعليمات البرمجية.ومع ذلك، أريد أن أرى ذلك في جافا.
يحرر:أوه نعم، سيكون من المفيد إظهار التنفيذ باستخدام إحدى هذه الهياكل (في Java).
المحلول
خريطة الشجرة يبدو لي أمرًا بديهيًا - ببساطة بسبب متطلبات "الترتيب الأبجدي".ليس لدى HashMap أي ترتيب عند التكرار من خلاله؛يتكرر TreeMap بترتيب المفاتيح الطبيعي.
يحرر:أعتقد أن تعليق كونراد ربما كان يقترح "استخدام hashmap ، ثم الفرز". هذا أمر جيد لأنه على الرغم من أنه سيكون لدينا تكرارات في البداية ، إلا أنه سيكون لدينا مفاتيح K <= N في النهاية بسبب التكرارات.قد نحتفظ أيضًا بالجزء الباهظ الثمن (الفرز) حتى النهاية عندما يكون لدينا عدد أقل من المفاتيح بدلاً من القيام بالضربة الصغيرة ولكن غير المستمرة المتمثلة في إبقائها مرتبة بينما نمضي قدمًا.
وبعد أن قلت ذلك، فأنا متمسك بإجابتي في الوقت الحالي:لأنه أبسط طريقة تحقيق الهدف .لا نعلم حقًا أن OP قلق بشكل خاص بشأن الأداء، لكن السؤال يشير إلى أنه مهتم بالأناقة والإيجاز.إن استخدام TreeMap يجعل هذا الأمر مختصرًا بشكل لا يصدق، وهو ما يروق لي.أظن أنه إذا كان الأداء يمثل مشكلة حقًا، فقد تكون هناك طريقة أفضل لمهاجمته من TreeMap أو HashMap :)
نصائح أخرى
يتفوق TreeMap على HashMap لأن TreeMap تم فرزه بالفعل من أجلك.
ومع ذلك، قد ترغب في التفكير في استخدام بنية بيانات أكثر ملاءمة، وهي حقيبة.يرىمجموعات العموم - و ال TreeBag فصل:
يحتوي هذا على بنية داخلية محسّنة وواجهة برمجة التطبيقات (API):
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
يحرر:تمت الإجابة على سؤال أداء HashMap مقابل TreeMap بواسطة Jon - HashMap وقد يكون الفرز أسرع (جربه!)، لكن TreeBag أسهل.وينطبق الشيء نفسه على الحقائب.يوجد HashBag بالإضافة إلى TreeBag.بناءً على التنفيذ (يستخدم عددًا صحيحًا قابلاً للتغيير)، يجب أن تتفوق الحقيبة على الخريطة العادية المكافئة لعدد صحيح.الطريقة الوحيدة لمعرفة ذلك على وجه اليقين هي الاختبار، كما هو الحال مع أي سؤال حول الأداء.
أرى عددًا لا بأس به من الأشخاص يقولون "يستغرق البحث في TreeMap O(n log n)"!!كيف ذلك؟
لا أعرف كيف تم تنفيذه ولكن في رأسي يستغرق الأمر O(log n).
وذلك لأنه يمكن إجراء البحث في الشجرة O(log n).لا تقوم بفرز الشجرة بأكملها في كل مرة تقوم فيها بإدراج عنصر فيها.هذه هي الفكرة الكاملة لاستخدام الشجرة!
ومن ثم، وبالعودة إلى السؤال الأصلي، فإن أرقام المقارنة هي:
نهج HashMap: O(n + k log k) الحالة المتوسطة، والحالة الأسوأ يمكن أن تكون أكبر من ذلك بكثير
نهج TreeMap: O(k + n log k) الحالة الأسوأ
حيث n = عدد الكلمات في النص، k = عدد الكلمات المميزة في النص.
يجب أن تكون خريطة التجزئة أسرع بكثير.يجب ألا تختار حاوية بناءً على الطريقة التي تريد بها ترتيب العناصر في النهاية؛فقط قم بفرز قائمة أزواج (الكلمة، التردد) في النهاية.عادةً ما يكون هناك عدد أقل من هذه الأزواج التي سيتم فرزها مقارنة بالكلمات الموجودة في الملفات، لذا سيكون الأداء المقارب (والحقيقي) مع خريطة التجزئة أفضل.
لا يمكنك تعيين أ TreeMap<String,Number> إلى متغير مع النوع Map<String,Integer>. Double, Long, ، إلخ.يمكن "وضعها" في أ TreeMap<String,Number>.عندما "أحصل" على قيمة من a Map<String,Integer>, ، يجب أن يكون Integer.
مع التجاهل التام لأي مشكلات تتعلق بـ i18n، وقيود الذاكرة، ومعالجة الأخطاء، إليك ما يلي:
class Counter {
public static void main(String... argv)
throws Exception
{
FileChannel fc = new FileInputStream(argv[0]).getChannel();
ByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
CharBuffer cb = Charset.defaultCharset().decode(bb);
Pattern p = Pattern.compile("[^ \t\r\n\f.,!?:;\"()']+");
Map<String, Integer> counts = new TreeMap<String, Integer>();
Matcher m = p.matcher(cb);
while (m.find()) {
String word = m.group();
Integer count = counts.get(word);
count = (count == null) ? 1 : count + 1;
counts.put(word, count);
}
fc.close();
for (Map.Entry<String, Integer> e : counts.entrySet()) {
System.out.printf("%s: %d%n", e.getKey(), e.getValue());
}
}
}
"عندما يكون مفتاح موجود بالفعل ، يكون له نفس الأداء مثل hashmap." - وهذا هو مجرد خطأ.يحتوي HashMap على إدراج O(1) وTreeMap O(n log n).سيستغرق الأمر على الأقل عمليات فحص n log n لمعرفة ما إذا كان موجودًا في الجدول!
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class TreeMapExample {
public static void main (String args[]){
Map<String,Integer> tm = new TreeMap<String,Integer>();
try {
FileInputStream fis = new FileInputStream("Test.txt");
DataInputStream in = new DataInputStream(fis);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String line;
int countValue = 1;
while((line = br.readLine())!= null ){
line = line.replaceAll("[-+.^:;,()\"\\[\\]]","");
StringTokenizer st = new StringTokenizer(line, " ");
while(st.hasMoreTokens()){
String nextElement = (String) st.nextElement();
if(tm.size()>0 && tm.containsKey(nextElement)){
int val = 0;
if(tm.get(nextElement)!= null){
val = (Integer) tm.get(nextElement);
val = val+1;
}
tm.put(nextElement, val);
}else{
tm.put(nextElement, 1);
}
}
}
for(Map.Entry<String,Integer> entry : tm.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
لهذه الطريقة، في رأيي، استخدام أفضل HashBag من مجموعات أباتشي كومنز أو HashMultiset من الجوافة أو HashBag من مجموعات الكسوف (رسميا مجموعات جي إس) أو أي الفئات التالية:
Order | Guava | Apache | Eclipse(GS) | JDK analog
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Not define | HashMultiset | HashBag | HashBag | HashMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Sorted | TreeMultiset | TreeBag | TreeBag | TreeMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Linked |LinkedHashMultiset| - | - | LinkedHashMap<String, Integere>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent & | ConcurrentHash- |Synchroniz-|Synchroniz- | Collections.synchronizedMap(
not define | Multiset | edBag | edBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent | - |Synchroniz-|Synchroniz- | Collections.synchronizedSorted-
and sorted | |edSortedBag| edSortedBag | Map(TreeMap<>))
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableMultiset|Unmodifiab-|Unmodifiab- | Collections.unmodifiableMap(
not define | | leBag | leBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableSorted- |Unmodifiab-|Unmodifiab- | Collections.unmodifiableSorted-
sorted | Multiset |leSortedBag| leSortedBag | Map(TreeMap<String, Integer>))
────────────────────────────────────────────────────────────────────────
أمثلة:
1. استخدام SynchronizedSortedBag من Apache:
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Bag bag = SynchronizedSortedBag.synchronizedBag(new TreeBag(Arrays.asList(INPUT_TEXT.split(" "))));
// Print count words
System.out.println(bag); // print [1:All!,2:Hello,1:Hi,2:World!]- in natural (alphabet) order
// Print all unique words
System.out.println(bag.uniqueSet()); // print [All!, Hello, Hi, World!]- in natural (alphabet) order
// Print count occurrences of words
System.out.println("Hello = " + bag.getCount("Hello")); // print 2
System.out.println("World = " + bag.getCount("World!")); // print 2
System.out.println("All = " + bag.getCount("All!")); // print 1
System.out.println("Hi = " + bag.getCount("Hi")); // print 1
System.out.println("Empty = " + bag.getCount("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.uniqueSet().size()); //print 4
2.استخدام TreeBag من Eclipse(GC):
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
MutableSortedBag<String> bag = TreeBag.newBag(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(bag); // print [All!, Hello, Hello, Hi, World!, World!]- in natural order
// Print all unique words
System.out.println(bag.toSortedSet()); // print [All!, Hello, Hi, World!]- in natural order
// Print count occurrences of words
System.out.println("Hello = " + bag.occurrencesOf("Hello")); // print 2
System.out.println("World = " + bag.occurrencesOf("World!")); // print 2
System.out.println("All = " + bag.occurrencesOf("All!")); // print 1
System.out.println("Hi = " + bag.occurrencesOf("Hi")); // print 1
System.out.println("Empty = " + bag.occurrencesOf("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.toSet().size()); //print 4
3. باستخدام LinkedHashMultiset من الجوافة:
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Multiset<String> multiset = LinkedHashMultiset.create(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(multiset); // print [Hello x 2, World! x 2, All!, Hi]- in predictable iteration order
// Print all unique words
System.out.println(multiset.elementSet()); // print [Hello, World!, All!, Hi] - in predictable iteration order
// Print count occurrences of words
System.out.println("Hello = " + multiset.count("Hello")); // print 2
System.out.println("World = " + multiset.count("World!")); // print 2
System.out.println("All = " + multiset.count("All!")); // print 1
System.out.println("Hi = " + multiset.count("Hi")); // print 1
System.out.println("Empty = " + multiset.count("Empty")); // print 0
// Print count all words
System.out.println(multiset.size()); //print 6
// Print count unique words
System.out.println(multiset.elementSet().size()); //print 4
المزيد من الأمثلة يمكنك العثور عليها في مشاريع جيثب الخاصة بي
سأختار بالتأكيد TreeMap:
- يقوم TreeMap تلقائيًا بفرز المفاتيح الجديدة عند الإدراج، ولا حاجة إلى الفرز بعد ذلك.
- عندما يكون المفتاح موجودًا بالفعل، يكون له نفس أداء HashMap.
يستخدم TreeSet داخليًا TreeMap، فلماذا لا تستخدم TreeMap مباشرة.
اعتمادًا على متطلبات السرعة، يمكنك أيضًا استخدام ملف حاول.ولكن ليس هناك فائدة من تنفيذ أحد هذه العناصر إذا كانت TreeMap سريعة بما فيه الكفاية.
ضع في اعتبارك تكرار الإضافة أو الحذف إلى بنية البيانات.لن يكون TreeMap مثاليًا إذا كان مرتفعًا.وبصرف النظر عن البحث عن الإدخال الحالي nLn، فإنه يخضع أيضًا لعملية إعادة توازن متكررة.
من ناحية أخرى، تكون هياكل التجزئة متوهجة بعض الشيء في الذاكرة (الإفراط في التخصيص).إذا كان بإمكانك عض تلك الرصاصة، فانتقل إلى بنية التجزئة وقم بالفرز عند الحاجة.
فيما يلي مثال جافا لقراءة ملف نصي، والفرز بناءً على المفتاح، ثم على القيم؛اعتمادا على عدد مرات ظهور الكلمات في الملف.
public class SortFileWords {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<String, Integer>();
ValueCompare vc = new ValueCompare(map);
TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(map);
List<String> list = new ArrayList<>();
Scanner sc;
try {
sc = new Scanner(new File("c:\\ReadMe1.txt"));
while (sc.hasNext()) {
list.add(sc.next());
}
sc.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
for (String s : list) {
if (map.containsKey(s)) {
map.put(s, map.get(s) + 1);
} else
map.put(s, 1);
}
System.out.println("Unsorted map: " + map);
sorted_map.putAll(map);
System.out.println("Sorted map on keys: " + sorted_map);
TreeMap<String, Integer> sorted_value_map = new TreeMap<>(vc);
sorted_value_map.putAll(map);
System.out.println("Sorted map on values: " + sorted_value_map);
}
}
class ValueCompare implements Comparator<String> {
Map<String, Integer> map;
public ValueCompare(Map<String, Integer> map) {
this.map = map;
}
@Override
public int compare(String s1, String s2) {
if (map.get(s1) >= map.get(s2))
return -1;
else
return 1;
}
}
لماذا لا تستخدم TreeSet?
نفس مفهوم الترتيب مثل TreeMap، باستثناء أنها مجموعة - والتي، حسب التعريف، هي "مجموعة لا تحتوي على عناصر مكررة".
من وصف مشكلتك، يبدو كما لو كنت بحاجة إلى مجموعة، ولا أرى ما هي المفاتيح والقيم التي تقوم بتعيينها معًا.
تطبق هذه الفئة واجهة Set، المدعومة بمثيل TreeMap.تضمن هذه الفئة أن المجموعة التي تم فرزها ستكون بترتيب تصاعدي للعناصر، مرتبة وفقًا للترتيب الطبيعي للعناصر (انظر المقارنة)، أو بواسطة المقارنة المقدمة في وقت الإنشاء المحدد، اعتمادًا على المنشئ المستخدم.
في الأساس يعتمد ذلك على المتطلبات.في بعض الأحيان تكون خريطة التجزئة جيدة وفي بعض الأحيان تكون الخريطة الشجرةية.ولكن من الأفضل استخدام خريطة التجزئة فقط لأنها تمثل بعض القيود على النفقات العامة لفرزها.
