ABA


"יש רעיונות איך לממש (למשל ב-Java), מערכת שמחזירה"
גירסת הדפסה        
קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15568 מנהל    סגן המנהל    מפקח   Winner    צל"ש   מומחה  
אשכול מספר 15568
ldan192 
חבר מתאריך 14.9.08
95119 הודעות
   19:33   21.11.09   
אל הפורום  
  יש רעיונות איך לממש (למשל ב-Java), מערכת שמחזירה  
 
ערכתי לאחרונה בתאריך 21.11.09 בשעה 19:37 בברכה, ldan192
 
מספר טבעי רנדומלי (מודולו MAX), אבל בלי חזרות, ב-(O(1?
חשבתי בהתחלה להשתמש ב-LinkedList שמאותחלים מ-0 עד MAX ואז כל פעם להוציא איבר ()i%size שיהיה רנדומלי וגם בלי חזרות.
הבעיה היא שהמתודה תקרא מאות פעמים ואתחול הרשימה המקושרת לא תהיה יעילה.
חשובה לי במיוחד הסיבוכיות מפני שהאלגוריתם עוצר אחרי זמן מסויים בכוח (וזה מורכב במיוחד עם שפה תקועה ואיטית כמו JAVA, כי צריך להשתדל כמה שיותר ליצור אטומיות בעצמי מבלי תמיד לדעת אילו בוודאות איזו מתודה/מבנה נתונים נתון יותר אטומיים מהאחר).

מבנה נתונים שמאתחל מבנה בסגנון ה-LinkedList שהזכרתי ב-(O(1?


בברכה,
עידן


                                שתף        
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

  האשכול     מחבר     תאריך כתיבה     מספר  
  לא פשוט בכלל לעשות דבר כזה. Deuce  21.11.09 21:43 1
     הנוסחא שהבאתי אכן עובדת. Deuce  21.11.09 21:51 2
         הםםם כן, חשבתי על האופציה הזו גם, הבעיה היא ldan192  22.11.09 00:10 3

       
Deuce 
חבר מתאריך 1.9.08
6225 הודעות
   21:43   21.11.09   
אל הפורום  
  1. לא פשוט בכלל לעשות דבר כזה.  
בתגובה להודעה מספר 0
 
גם הגרלה מהירה וגם לא לחזור על ערכים? לא פשוט.
אם באמת יש לך זכרון גדול אז אפשר להקצות מערך, נקרא לו מערך היחידה שמקיים A = i ולעשות עליו פרמוטציה ב-O(n) ויש לך RANDOM GENERATOR שבקריאה ה-iית מחזיר לך את המספר בתא ה-iי.

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


Xn+1 = (Xn + p) % max

כלומר תבחר p ראשוני ו-X0 סתם מספר בטווח.
(אני אבדוק את זה בעצמי שנייה)

אם לא חשוב לך שלא יהיו חזרות, אז אפשר להשתמש בנוסחא למחולל מספרים כמו ב-C.







                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
Deuce 
חבר מתאריך 1.9.08
6225 הודעות
   21:51   21.11.09   
אל הפורום  
  2. הנוסחא שהבאתי אכן עובדת.  
בתגובה להודעה מספר 1
 
טוב, זה לא כזה מפתיע אבל רציתי לבדוק בקוד.

#include <stdio.h>

int main(void)
{
int range = 1200;
int p = 13;
int x0 = 20;
int i = 0, j = 0;
int Xn = x0;
int ar;
int count;
for (; i < range; ++i)
{
/*printf("%d ", Xn);*/
ar = Xn;
Xn = (Xn + p) % range;
}

for (i = 0; i < range; ++i)
{
count = 0;
for (j = 0; j < range; ++j)
{
if (ar == i)
count++;
}
if (count != 1)
printf("%d", i);
}
return 0;
}


אכן הגריל כל מספר פעם אחת.






                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
ldan192 
חבר מתאריך 14.9.08
95119 הודעות
   00:10   22.11.09   
אל הפורום  
  3. הםםם כן, חשבתי על האופציה הזו גם, הבעיה היא  
בתגובה להודעה מספר 2
 
שמרוב חישובים עדיף לי פשוט להשתמש במערך בוליאני באורך n וכל פעם אם בחרתי את המספר לבצע continue, זה עדיין פחות חישובים.
קיוויתי אבל שיש איזשהו מבנה נתונים ב-Java שאולי אני לא מכיר שמאפשר לאתחל אותו פעם אחת ואז להסיר ממנו איברים בדומה לרשימת מקושרת.
גם חשובה לי מאוד רנדומליות מלאה (עד כמה שאפשר, כלומר תלויית שעון).
אני אנסה לראות אם אצליח לפתח את הרעיון שלך יותר מחר, אולי באמת זה רעיון טוב להסתמך על שדות לפי (GF(P.

THX


בברכה,
עידן


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

תגובה מהירה  למכתב מספר: 
 
___________________________________________________________________

___________________________________________________________________
למנהלים:  נעל | תייק בארכיון | מחק | העבר לפורום אחר | מחק תגובות | עגן אשכול
       



© כל הזכויות שמורות ל-רוטר.נט בע"מ rotter.net