שלום
אשמח אם תביאו לי רעיונות בפתרון הבעיה:

רשום פונקציה שמקבלת שתי מערכים עם מספרים, והפונקציה תחזיר מערך עם מספרים שנמצאים רק באחד המערכים ולא בשניהם
דוגמא-
מערך ראשון - 2 5 66 8 90
מערך שני- 90 43 66 5 2 923

אז הפונקציה תחזיר-
8 43 923

אני צריך את זה בפתרון הכי יעיל שאפשר

תודה רבה!!
ארנון

הייתי מביא לך את הפונקציה php_array_diff שנמצאת בספריית הפונקציות של PHP, אבל היא מלאה בכ"כ הרבה דברים שאתה לא צריך שעדיף כבר שלא...
ד"א אם אתה מעוניין היא נמצאת בקובץ array.c שבתיקייה ext\standard (צריך לפני כן להוריד את ה-source code של PHP...).

הפיתרון האינטואיטיבי ביותר זה לעבור על המערך ולבדוק כל איבר מול איבר במערך השני.
כדי שלא תצטרך לעשות זאת שוב עבור המערך השני, תעשה מערך של flags עבור האיברים במערך השני, כל מפתח במערך flags יציין את המפתח שבמערך השני, כאשר ה-value יהיה מסוג boolean ויעיד אם האיבר קיים במערך הראשון או לא....

אני לא מבין על איזה מפתח אתה מדבר? האם ניתן לעשות את זה בC?

כן בודאי שניתן ב-C.

במפתח הכוונה ל- key כלומר האינדקס.

דוגמא:

קוד:

int num = {68,21,0};
int key;

for (key=0; key<3; ++key)
  printf("In key #%d the value is: %d", key, num[key]);

סבבה הבנתי מה זה מפתח רק שאחרי הnum היית צריכה סוגריים מרובעות

אבל עדין לא הבנתי את האלגוריתם שלך, מה הכוונה 'לבדוק איבר מול איבר', המערכים לא ממוינים , אז עדיין זה יהיה בסיבוכית של N^2(עבור כל איבר במערך הראשון בודקים N איברים של המערך שני..
)

עדיין איני בטוח שהבנתי מהו המושג "סיבוכיות" אבל האם לא התכוונת לסיבוכיות של m*n?
כאשר m זה גודל איבר ראשון ו-n גודל איבר שני...

בדיקה של איבר מול איבר מתבצע בצורה הבאה:
על כל איבר במערך הראשון, תעשי בדיקה על כל האיברים שבמערך השני (אם הם שווים אליו).
כך את עוברת על כל האיברים במערך הראשון...

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


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

אה! בעצם...
יש לנו את פעולת הכפל.
תוכלי בתחילה לכפול את כל האיברים במערך הראשון, כך:

קוד:

2*5*66*8*90

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

עריכה: בעצם רעיון (האחרון) טיפשי ויספק טעות...

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

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

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

בברכה, מתן.
www.MatanNarkiss.com