מה המפרט המומלץ לאלגוריתמיקה בC++?

[Boomerang]

אתה יכול להסביר בקצת יותר פירוט מה אתה מנסה להריץ? (מה זה פונקציה שמחזירה תוצאות לא רציפות? פונקציה בנקודה היא רציפה או לא רציפה)

רוב הסיכויים שהשיפור הגדול בביצועים לא יבוא על מחשב קצת יותר חזק אלא ע"י בשימוש באלגוריתמים יותר יעילים.

יש ספריות (כמו MKL של אינטל) שמאיצות חישובים מדעיים (פעולות על מטריצות, טרנספורמציות, וכו') שיכולות לעזור לך בזה.

[lharpaz]

אני לא יכול להשתמש בקירובים כאלה ואחרים מכיוון שמדובר בפונקציות שנותנות תשובות לא רציפות. כל יחידה במשתנה יכולה לעשות את כל ההבדל.

אני לא מבין על מה בדיוק אתה מדבר, אז אני לא יכול להגיד שקירובים הם מספיק טובים, אבל רק שתדע שיש כל מיני קירובים שנחשבים בסדר גמור. כמובן שזה תלוי גם בשימושים המדוייקים שלך ובכמה מדוייק אתה צריך שדברים יהיו. (אני למשל לקחתי מקסימום מבין המון אטירציות של אלגוריתם חמדן עם מוטיב רנדומי. בשבילי זה היה מספיק טוב לפתרון בעיית אופטימיזציה של ILP).

בכל מקרה, אני חוזר ומציע לעשות הערכת זמן לגבי הריצה. אולי תראה שאין מצב לפתור את זה גם עם מחשבים חזקים מאוד (2 בחזקת 46 איטרציות זה הרבה מאוד, ואם אתה עושה לא מעט דברים בכל איטרציה אז זה בערך לא פתיר). [וכמובן - חשוב לבדוק את עניין הזיכרון].

בכל מקרה, עוד רעיון שהיה לי, בגלל שאין לך אפשרות להריץ על מחשבים רציניים, תנסה לכתוב את התוכנית ככה שהיא תוכל לרוץ בתהליכים נפרדים לגמרי, על מחשבים נפרדים לגמרי. ככה תוכל "לחלק" לחברים שלך קבצים להרצה. למשל, מריצים בלילה לפני שהולכים לישון, ואם זה מסתיים עד שחוזרים מהעבודה אז תוכל לנצל ככה כוח מחשוב של כמה מחשבים בלי לקנות שום דבר. זה כמובן לא יעבוד אם מה שאתה רוצה להריץ צריך לרוץ כל הזמן...

אתה יכול להסביר בקצת יותר פירוט מה אתה מנסה להריץ? (מה זה פונקציה שמחזירה תוצאות לא רציפות? פונקציה בנקודה היא רציפה או לא רציפה)

רוב הסיכויים שהשיפור הגדול בביצועים לא יבוא על מחשב קצת יותר חזק אלא ע"י בשימוש באלגוריתמים יותר יעילים.

יש ספריות (כמו MKL של אינטל) שמאיצות חישובים מדעיים (פעולות על מטריצות, טרנספורמציות, וכו') שיכולות לעזור לך בזה.

אני לא יודע אם הוא התכוון לזה, אבל אתה יודע מה זה ILP = integer linear programing ? מדובר באופטימיזציה של כמה משתנים, אשר יכולים לקבל ערכים של מספרים שלמים בלבד. הבעיה הזו היא NP-קשה. יעני, ממש קשה. מאמינים שלא ניתן לפתור אותה במדוייק בזמן פולינומיאלי באורך הקלט. כמובן שמבחינה אלגוריתמית אפשר לייעל הרבה דברים ולהפוך אותם למהירים יותר, אבל אי אפשר לעשות את זה לבעיות NP-קשות.

TheWiz - אולי באמת תפרט יותר בקשר למה שאתה עושה ולמה בדיוק התכוונת בקשר לפונק' עם תוצאות לא רציפות.

אולי נוכל לעזור, ובלי קשר לזה, זה נשמע מאוד מעניין (שיהיה בהצלחה!)

[TheWiz]

אז ככה. אני מנתח טכני ובכדי לסחור בצורה טובה יותר אני מפתח מערכת סטיסטיות שמחשבות את הסיכויים לעליה או ירידה של מוצר זה או אחר.

כמובן שעשיתי את האלגורתמים עצמם מאוד יעילים בכדי לפשט את הדברים אבל אין לי אפשרות לבצע קירוב מכיוון שהפרמטרים אינם קשורים אחד לשני ישירות אלא דרך מספר משוואות ופעולות בינהם. אני אסביר לדוגמא אני עושה חישוב של ממוצע נע לאורך תקופה מסויימת ואני בודק האם מתבצע חיתוך מול ממוצע של מתנדד בשם RSI. כל אחד מהם מקבל 2-3 פרמטרים שאינם קשורים בינהם. ולכן אני לא רואה דרך כיצד לבצע קירוב. או שהם נפגשים או שהם לא נפגשים בנק' זמן מסויימות.

הפעולות שאני מבצע אינן פעולות בסיסיות בין מטריצות או דברים קיימים. אלה כלים שאני מפתח ומשכלל.

המערכת בנויה כך שהיא מדפיסה לקובץ וממשיכה שאני מתחיל אותה שוב. זאת לא הבעיה.

[Boomerang]

הטרנספורמציות שאני דיברתי עליהן הם פורייה, אדאמר ודומיהן, מציאת ערכים עצמיים ועוד די הרבה פעולות מורכבות. נראה לי ששווה לך להעיף מבט לראות אם זה יכול להיות שימושי לך.

אם יש לך דרך למקבל תהליכים, יש גם תחום שצובר פופולריות להרצת אלגוריתמים על גבי כרטיס המסך (בעזרת vertex/pixel shaders)

ניסית להריץ את התוכנית שלך עם פרופיילר כדי לוודא שרוב הזמן הולך על חישובים נטו ולא על דברים כמו קריאה/כתיבה לדיסק?

עוד דבר - אני יודע שבמרכז המחשבים באוניברסיטה העברית משכירים זמן חישוב על מערכת ההפעלה המבוזרת שלהם (Mosix) אולי זה יעזור לך.