کاربرد Multiset در جاوا

  • 16/آبا/1394
  • سیّد

Multiset یکی از کلاس‌های کتابخونه‌ی guava هست. این کتابخونه که گوگل برای زبان جاوا منتشرش کرده، شامل کلاس‌های کمکی مختلفی برای کارهای پایه‌ای در جاوا هست، شامل تعدادی data structure جدید که یکی از اونها Multiset هست. توی این پست می‌خوایم در مورد Multiset صحبت کنیم.

احتمالاً برای شما هم زیاد پیش اومده که بخواین تعداد یه سری موجود رو توی یه مجموعه بشمرید. مثال کاملاً کاربردیش اینه که می‌خوایم کلمات موجود در یک متن رو با تعداد تکرارشون استخراج کنیم. برای این کار چی کار می‌کنیم؟ اول فرض کنید متن رو توسط Space جدا می‌کنیم تا کلماتش استخراج بشه (می‌شه خیلی پیچیده‌ترش کرد، مثلاً «نقطه» و «ویرگول» رو هم در نظر بگیریم، حروفی مثل «ك» و «ي» رو normal کنیم، و ...، ولی توی این پست به این مباحث نمی‌پردازیم). پس یه []String داریم، فرض کنید اسمش هست words. حالا برای این که تعداد کلمات رو توش بشمریم، می‌تونیم یه Map تعریف کنیم، از String به تعداد. یه فرض منطقی می‌تونیم بکنیم، که تعداد هر کلمه توی متن بیش از ۲ میلیارد نیست! پس int براش کافیه.
همونطور که می‌دونید، توی جاوا نمی‌شه از primitive type ها به عنوان generic type استفاده کرد. یعنی یه کلاسی مثل Map که Key و Value اون از نوع generic هستن و شما موقع تعریف متغیرتون نوعشون رو مشخص می‌کنید، نمی‌تونید برای Key و Value از مثلاً int استفاده کنید، بلکه مجبورید برای عددی کردنش از Integer یا Long استفاده کنید (البته کتابخونه‌هایی مثل HPPC برای این که بتونید از primitive type ها در این جور مواقع استفاده کنید وجود دارن). بنابراین متغیری که اینجا تعریف می‌کنیم، به این صورت می‌شه:


Map<String, Integer> wordsMap = new HashMap<>();

حالا روی کلمات حرکت می‌کنیم و هر کدومشون رو بررسی می‌کنیم که قبلاً دیدیمش یا نه. اگه ندیدیمش، یعنی توی Map نیست، براش مقدار «یک» رو توی Map قرار می‌دیم. اگه دیدیمش، مقدار قبلیش رو می‌گیریم، بعلاوه‌ی یک می‌کنیم، می‌ذاریم توی Map.


for (String word : words) {
    if (!wordsMap.containsKey(word)) {
        wordsMap.put(word, 1);
    }
    else {
        Integer oldValue = wordsMap.get(word);
        wordsMap.put(word, oldValue + 1);
    }
}

توی این کدی که زدیم چند تا اشکال هست. اول از همه این که توی Map مون داریم ۲ بار دنبال داده می‌گردیم (یه بار با containsKey و یه بار هم با get) و در نتیجه هزینه‌اش رو ۲ بار می‌دیم (درسته که نگاه کردن یه المان توی Map سرعت بالایی داره و (1)O هست، ولی وقتی توی یه حلقه هی تکرارش می‌کنید بالاخره داره سرعت رو پایین میاره). برای این که این مشکل رو حل کنیم، می‌تونیم یه بار همون اول get کنیم، در صورتی که مقدار null برگردونده بشه یعنی توی Map نبوده و در صورتی که مقدار غیر null باشه یعنی مقدار قبلی داشته:


for (String word : words) {
    Integer oldValue = wordsMap.get(word);
    if (oldValue == null) {
        wordsMap.put(word, 1);
    }
    else {
        wordsMap.put(oldValue + 1);
    }
}

اشکال دیگه‌ای که اینجا وجود داره، اینه که داخل هر خونه‌ی این Map ما، یه Object هست، نه یه primitive type. برای همین وقتی شما می‌نویسید:


wordsMap.put(oldValue + 1);

این دستور باعث می‌شه اول از oldValue که یه شیء Integer هست، intValue فراخوانی بشه (به صورت خودکار)، بعد بعلاوه‌ی یک بشه، بعد Integer.valueOf روش عدد به دست اومده فراخوانی بشه (باز هم به صورت خودکار) و در نهایت یه شیء Integer توی Map ما put بشه. به این تبدیل primitive به شیء و بالعکس که به صورت خودکار انجام می‌شه، می‌گن auto-boxing. مهم این بخش آخر هست که برای هر entry توی این Map، داریم یه شیء Integer می‌سازیم و این سربار نسبتاً زیادی داره.
البته یه کلاسی توی جاوا وجود داره به نام IntegerCache. وقتی auto-boxing انجام می‌شه، همونطور که گفتم به جای این که مستقیماً (new Integer(n فراخوانی بشه، (Integer.valueOf(n فراخوانی می‌شه. اگه داخل کد این تابع رو نگاه کنید، می‌بینید که اول چک می‌کنه می‌تونه از IntegerCache استفاده کنه یا نه. توی این کلاس یه تعداد محدودی از اشیاء Integer توی یه آرایه cache شدن که دیگه هی new نشن. کلاس Integer یه کلاس Immutable هست، یعنی بعد از ساخته شدن، دیگه نمی‌تونید مقدارش رو عوض کنید. برای همین توابعی مثل add یا increment نداره (برای همین هست که هر بار که توی کد بالا مقدار رو می‌خوایم یکی زیاد کنیم، کل این داستان‌ها که گفتم اتفاق می‌افته). به خاطر همین موضوع، می‌شه اشیائش رو توی برنامه share کرد و ازشون همه جا به صورت مشترک استفاده کرد. همین اتفاق داره توی این cache که گفتم می‌افته و یه range خیلی کوچک از Integer ها (پیش‌فرضش از ۱۲۸- تا ۱۲۷ هست، می‌شه توسط پارامتر XX:AutoBoxCacheMax=size- موقع اجرای جاوا حد بالاش رو تغییر داد) توی یه آرایه هستن که توی Integer.valueOf اگه عدد ورودی توی این range مشخص باشه، ازشون استفاده می‌کنه، و اگه نباشه یه شیء Integer براتون new می‌کنه.
کل این داستانی که گفتم باعث می‌شه که تا وقتی اون تعداد که داریم توی کدمون می‌شمریم از حد بالای این cache (که به صورت پیش‌فرض ۱۲۷ هست) بیشتر نشده، سرباری برامون نداشته باشه.

حالا اگه بخوایم به هر دلیلی (مثلاً اگه تعدادی که می‌شمریم از ۱۲۷ بیشتر بشه) از این قضیه فرار کنیم، می‌تونیم به جای این کار، از یه کلاس Integer استفاده کنیم که Mutable باشه، و هر بار به جای این که بریم و از اول یه شیء جدید توی Map مون put کنیم، همون شیء قبلی رو بگیریم و مقدار داخلش رو یکی زیاد کنیم. برای این کار می‌تونیم خودمون یه کلاس ساده‌ی MutableInteger بنویسیم، یا از کتابخونه‌های موجود استفاده کنیم. مثلاً apache commons lang کلاس MutableInt داره. یا اگه می‌خواین کدتون thread-safe باشه، می‌تونید از AtomicInteger خود جاوا استفاده کنید. من مثال رو با کلاس MutableInteger فرضی جلو می‌برم:


for (String word : words) {
    MutableInteger oldValue = wordsMap.get(word);
    if (oldValue == null) {
        wordsMap.put(word, new MutableInteger(1));
    }
    else {
        oldValue.increment();
        // یا
        oldValue.add(1);
    }
}

همچنین دقت کنید که این روش، یه put هم کمتر داره. یعنی در حالتی که مقدار قبلی توی Map موجود بوده، دیگه put نمی‌زنیم (خود put هم مثل get هزینه‌ی (1)O داره، در کنار این که خود تابع put کلی کار اضافه انجام می‌ده که می‌تونید توی کدش ببینید)، و فقط در حالتی که اولین بار یه کلمه رو دیدیم و مقدار «یک» رو می‌خوایم توی Map قرار بدیم، یه put داریم. پس در بعضی حالات با یه حرکت (1)O و در بعضی حالات با ۲ تا حرکت (1)O کار رو جلو می‌بریم.
حالا همین کد رو هم می‌شه یه مقدار بهینه‌تر کرد. می‌تونیم به جای یه get و بعضی وقتها یه put، کلاً یه put داشته باشیم (ایده‌ی کلی این بخش رو از اینجا گرفتم (البته روش پایین کارآمدتر از روش منبع ذکر شده هست): http://blog.pengyifan.com/most-efficient-way-to-increment-a-map-value-in... ):


MutableInteger tempValue = new MutableInteger(1);
for (String word : words) {
    MutableInteger oldValue = wordsMap.put(word, tempValue);
    if (oldValue == null) {
        tempValue = new MutableInteger(1);
    }
    else {
        tempValue.add(oldValue.get());
        tempValue = oldValue;
        tempValue.set(1);
    }
}

مسئله‌ی بعدی‌ای که توی این کد وجود داره، اینه که یه مشت شیء از نوع Integer اون وسط ریخته! هر شیئی که توی جاوا ساخته می‌شه، یه سری سربار داره: یکی سرباری که خود شیء داره، و یکی سرباری که اشاره‌گر به اون شیء توی ساختارهایی مثل Map داره. شما هر داده‌ی جدیدی داخل Map قرار بدید، یه شیء از نوع Entry براش ساخته می‌شه، که یه اشاره‌گر به یه شیء برای کلید داره، و یه اشاره‌گر به یه شیء برای مقدار. بنابراین کلاً همه‌اش شد سربار! :)
چی کار کنیم که این سربارها به وجود نیاد؟ خوب بهترین کار اینه که اگه بتونیم، به جای Integer، از int که یه primitive type هست استفاده کنیم. چطوری؟ می‌تونیم از کتابخونه‌هایی مثل HPPC یا trove4j استفاده کنیم. یه راه دیگه، استفاده از Multiset هست. کلاس Multiset اصلاً برای همین کار ساخته شده! می‌تونید یه Multiset از String بسازید:


Multiset<String> wordsSet = HashMultiset.create();

و بعد کلماتتون رو خیلی راحت توش اضافه کنید:


for (String word : words) {
    wordsSet.add(word);
}

و در نهایت هم توسط تابع entrySet فهرست کلمات رو به همراه تکرارشون بگیرید:


for (Multiset.Entryentry : wordsSet.entrySet()) {
    System.out.println(entry.getElement() + ": " + entry.getCount());		    
}

در نهایت این رو بگم که کتابخونه‌ی guava کلاً کتابخونه‌ی به درد بخوریه! حتماً بخش‌های مختلفش رو یه نگاه بندازید (حتی بخشی از spec زبان جاوا نسخه‌ی ۸ از روی ایده‌های guava کپی شده).

اضافه کردن دیدگاه جدید

Plain text

  • تگ های HTML قابل قبول نمی باشد.
  • آدرس های وب و ایمیل به صورت اتوماتیک به لینک تبدیل می شوند.
  • خطوط و پاراگرافها به صورت اتوماتیک جدا سازی می شود.