streamalism.org

1. הקדמה

במדריך מהיר זה נחקור דרכים שונות להשיג את מספר הספרות ב- מספר שלם בג'אווה.

ננתח גם את השיטות השונות ונבין איזה אלגוריתם יתאים ביותר למצבנו.

2. מספר הספרות ב- מספר שלם

לשיטות הנדונות כאן, אנו שוקלים רק מספרים שלמים חיוביים. אם אנו מצפים לכל קלט שלילי, ראשית נוכל להשתמש בו Math.abs (מספר) לפני שתשתמש באחת משיטות אלה.

2.1. חוּט-פתרון מבוסס

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

אורך int = String.valueOf (number) .length ();

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

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

2.2. גישה לוגריתמית

עבור המספרים המיוצגים בצורה עשרונית, אם ניקח את היומן שלהם בבסיס 10 ונעגל אותו כלפי מעלה, נקבל את מספר הספרות במספר זה:

אורך int = (int) (Math.log10 (number) + 1);

ציין זאת עֵץ₁₀0 של מספר לא מוגדר. אז אם אנו מצפים לכל קלט עם ערך 0ואז נוכל לבדוק גם את זה.

הגישה הלוגריתמית מהירה משמעותית מ חוּט גישה מבוססת מכיוון שהיא לא חייבת לעבור תהליך של המרת נתונים כלשהי. זה פשוט כולל חישוב פשוט ופשוט ללא שום אתחול אובייקטים או לולאות נוספות.

2.3. כפל חוזר

בשיטה זו ניקח משתנה זמני (מאותחל ל -1) ונכפיל אותו ברציפות עם 10 עד שהוא נהיה גדול יותר ממספרנו. במהלך תהליך זה נשתמש גם ב- אורך משתנה שישמור על מעקב אחר אורך המספר:

אורך int = 0; טמפ 'ארוכה = 1; ואילו (temp <= number) {אורך ++; temp * = 10; } אורך החזרה;

בקוד זה, השורה טמפ * = 10 זהה לכתיבה temp = (temp << 3) + (temp << 1). מכיוון שכפל הוא בדרך כלל פעולה יקרה יותר במעבדים מסוימים בהשוואה למפעילי משמרות, ייתכן שהאחרון יעיל מעט יותר.

2.4. מתחלק בכוחות של שניים

אם אנו יודעים על טווח המספר שלנו, נוכל להשתמש בווריאציה שתפחית עוד יותר את ההשוואות שלנו. שיטה זו מחלקת את המספר בכוחות של שניים (למשל 1, 2, 4, 8 וכו '):

שיטה זו מחלקת את המספר בכוחות של שניים (למשל 1, 2, 4, 8 וכו '):

אורך int = 1; אם (מספר> = 100000000) {אורך + = 8; מספר / = 100000000; } אם (מספר> = 10000) {אורך + = 4; מספר / = 10000; } אם (מספר> = 100) {אורך + = 2; מספר / = 100; } אם (מספר> = 10) {אורך + = 1; } אורך החזרה;

הוא מנצל את העובדה שכל מספר יכול להיות מיוצג על ידי הוספת כוחות של 2. לדוגמא, ניתן לייצג 15 כ- 8 + 4 + 2 + 1, שכולם כוחות של 2.

עבור מספר בן 15 ספרות, היינו מבצעים 15 השוואות בגישה הקודמת שלנו, שהפחתנו ל -4 בלבד בשיטה זו.

2.5. הפרד ומשול

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

אנו מקבלים את התשובה בשלושה או ארבעה פשוטים אם הצהרות:

אם (מספר <100000) {אם (מספר <100) {אם (מספר <10) {החזר 1; } אחר {להחזיר 2; }} אחר {אם (מספר <1000) {להחזיר 3; } אחר {אם (מספר <10000) {חזרה 4; } אחר {לחזור 5; }}}} אחר {אם (מספר <10000000) {אם (מספר <1000000) {להחזיר 6; } אחר {חזרה 7; }} אחר {if (מספר <100000000) {החזר 8; } אחר {אם (מספר <1000000000) {החזר 9; } אחר {לחזור 10; }}}}

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

3. מידוד

כעת, כשיש לנו הבנה טובה של הפתרונות הפוטנציאליים, בואו נעשה מיד ביצוע פשוט של כל השיטות שלנו באמצעות רתמת Java Microbenchmark (JMH).

הטבלה הבאה מציגה את זמן העיבוד הממוצע של כל פעולה (בשניות ננו):

יחידות מידה Cnt ציון שגיאות יחידות Benchmarking.stringBasedSolution avgt 200 32.736 ± 0.589 ns / op Benchmarking.logarithmicApproach avgt 200 26.123 ± 0.064 ns / op Benchmarking. RepeatedMultiplication avgt 200 7.494 ± 0.207 ns / op Benchmarking.dividingWithpowers 200 Benchmarking.divideAndConquer ממוצע 200 0.956 ± 0.011 ns / op

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

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

כפל חוזר כולל כפל פשוט, ביחס לאורך המספר; לדוגמא, אם המספר באורך חמש עשרה ספרות, שיטה זו תכלול חמש עשרה כפלות.

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

לבסוף, כפי שאנו יכולים להסיק, האלגוריתם היעיל ביותר הוא היישום המפורש של Divide and Conquer - שמספק את התשובה בשלוש או ארבע אמירות פשוטות אם. אנו יכולים להשתמש בו אם יש לנו מערך נתונים גדול של מספרים שעלינו לנתח.

4. מסקנה

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

וכמו תמיד, תוכל למצוא את הקוד השלם ב- GitHub.