نیاز به راهنمایی برای حل پروژه

[mohammaddx]

با سلام به همه ی جاواکاران عزیز.
من از مبتدیان جاوا هستم و برای پروژه دانشگاه نیاز به کمک فوری شما دارم.
یه فایل تکست سنگین چند میلیون خطی (8 گیگ) دارم که سه ستون داره و در هر ستون عددهایی هست.
چیزی که از من خواسته شده:
***برای این فایل مشخص کنید که چه تعداد سطر با مقدار ستون سوم متفاوت وجود دارد که مقادیر ستون اول آنها با هم برابر و مقادیر ستون دوم آنها نیز با هم برابر است. به عبارت یگر:
Ri.colm1=Rj.colm1&&Ri.colm2=Rj.colm2 && Ri.colm3<>Rj.colm3
مقدار ستون سوم زمان رویت یال را مشخص می‌کند. مورد بالا در واقع می‌خواهد چک کند که آیا یالی وجود دارد که در دو زمان متفاوت رویت شده باشد؟*****
-------------
از دوستان درخواست راهنمایی دارم تا ایده های تئوری خودشون را برای حل این مسئله بدن.با تشکر

[-سیّد-]

سلام
چند تا سؤال:
- فرمت فایل شما چیه؟ binary یا text؟ تو هر حالت، ۳ تا ستون چطوری نوشته شدن؟ مثلاً csv هست؟ یا json؟ یا protobuf؟ یا فرمت باینری custom؟
- اندازه‌ی گراف شما چقدره؟ یعنی تعداد node ها و یال‌های گرافتون چقدره؟
- range اعداد استفاده شده در گراف چیه؟ (جواب این سؤال در واقع از ترکیب جواب ۲ سؤال قبلی به دست میاد) یعنی شماره‌ی یه node از چند تا چنده؟ همچنین ستون سوم که زمان هست توی چه فرمتی هست؟ timestamp هست؟
- هدف فقط شمردن تعداد یال‌هایی هست که در زمان‌های مختلف دیده شدن؟ یعنی فهرستشون رو نمی‌خوایم؟ خروجی برنامه باید یک عدد خالی باشه؟
- چه سخت‌افزاری در اختیار دارید؟ مخصوصاً چقدر RAM می‌تونید استفاده کنید؟
- آیا در استفاده از کتابخانه‌ها و سرویس‌های آماده محدودیتی دارید؟ (مثلاً MySql)

پیشاپیش بگم چرا این سؤالا رو می‌پرسم:
۲ راه حل کلی به نظرم می‌رسه:
- استفاده از یه فریم‌ورک یا کتابخونه‌ی موجود
- نوشتن از پایه
می‌خوام ببینم اگه داده‌هاتون بزرگن و شاید قراره بزرگ‌تر هم بشن (مثلاً اگه پروژه فازهای بعدی‌ای داره، یا اگه قراره به یه کار واقعی تبدیل بشه)، می‌تونید مثلاً از فریم‌ورک MapReduce استفاده کنید، که تا بینهایت رو پشتیبانی می‌کنه و نگران این نیستید که اگه حجم گراف از فلان مقدار بزرگتر شد باید سیستم رو تغییر بدید! برای مثال، گراف وب ما در موتور جستجوی یوز، خیلی وقت پیش که آمارش رو داشتم، نزدیک ۱۳ میلیارد node داشت، و نزدیک ۳۰۰ میلیارد یال. (الان نمی‌دونم آمارش چقدره) حجم هم ترابایتی بود. گراف وب لحظه به لحظه بزرگتر می‌شه (هم به خاطر صفحات جدیدی که توی وب تولید می‌شن، هم به خاطر صفحاتی که برای خزشگر ما جدیده، چون ما هنوز درصد زیادی از وب انگلیسی رو خزش نکردیم)، و ما باید پیش‌بینی آینده رو بکنیم و یه سیستم scalable داشته باشیم. الان سیستممون طوریه که با اضافه کردن سخت‌افزار، به سادگی می‌تونیم تا صدها برابر این حجم رو پشتیبانی کنیم.
اما اگه مقیاس کار در حدی نیست که نیاز به MapReduce باشه، می‌تونید خودتون رو درگیر ریزه‌کاری‌های اون نکنید (البته MapReduce موجود بسیار جالبیه و وقتی که بهش عادت کنید ازش خوشتون میاد). مثلاً بسته به حجم کار (اعدادی که بالاتر پرسیدم) و میزان حافظه‌ای که در اختیار دارید ممکنه بتونید خیلی ساده‌تر با یه ساختاری مثل hppc و به صورت in-memory این کار رو انجام بدید.

[ahmad.mo74]

سلام

حرف آقا سیّد درسته و شما اطلاعات خیلی کمی دادید در مورد نوع داده و نحوه پردازش و ... دادید.
و اینکه انجام پروژه دانشگاهیتون رو اینجا نباید درخواست کنید و در کل کار درستی نیست. لااقل خودتونم تلاش میکردید و راه هایی که رفتید و تست کردید رو اینجا مطرح می کردید.

راهنمایی ای که میتونم بکنم اینه که اگر قرار نیست از هیچ فریم ورک خاصی استفاده کنی، برای خوندن فایل به این بزرگی میشه خیلی راحت از BufferedReader استفاده کرد که توی 99 درصد مواقع سریعترین راه هست. اما همراه با NIO چیزی معرفی شد به اسم memory-mapped files و کلاس MappedByteBuffer هم براش نوشته شده (با MappedByteBuffer نمیشه بیشتر از 31^2 رو بایت رو خوند و باید از چندین MappedByteBuffer استفاده بشه) که تو حجم بالا خیلی سریع تر عمل میکنه.

توضیحات بشتر :

http://javarevisited.blogspot.com/2012/01/memorymapped-file-and-io-in-java.html
http://www.javacodegeeks.com/2013/05/power-of-java-memorymapped-file.html
http://howtodoinjava.com/2015/01/16/java-nio-2-0-memory-mapped-files-mappedbytebuffer-tutorial/
http://www.codeproject.com/Tips/683614/Things-to-Know-about-Memory-Mapped-File-in-Java

برای پیدا کردن خطوطی که اون شرط مورد نظرو باید داشته باشن هم میتونی از یه Map استفاده کنی و زمان (ستون سوم) رو به عنوان کلید بهش بدی (زمان های مشابه حذف میشه اینطوری) و ستون هایی که مربوط به اون ردیف هست رو هم بهش مپ کنی (مثلا آرایه ای از String باشه).
بعدش باید روی این مپ پردازش انجام بدی تا جواب نهایی رو بگیری.
مثلا یک بار تمام ردیف هایی که ستون اولشون با هم برابره رو پیدا کنی بعد از بین اینا ردیف هایی که ستون دومشون هم با هم برابر هست رو جدا کنی.
(راهنمایی : اگر از Stream API استفاده کنی خیلی کارت راحتتر میشه)

[-سیّد-]

اینطوری نظم اینجا به هم می‌ریزه. لطفاً یه سؤال کاملاً بی‌ربط رو زیر یه بحث دیگه مطرح نکنید. من جواب رو توی thread مخصوص سؤالتون دادم:
http://barnamenevis.org/showthread.php?511943-%D9%86%DB%8C%D8%A7%D8%B2-%D8%A7%D8%B8%D8%B7%D8%B1%D8%A7%D8%B1%DB%8C-%D8%AD%D9%84-%D9%BE%D8%B1%D9%88%DA%98%D9%87&p=2278511&viewfull=1#post2278511