SDL 0210 - Mobile Manager Dynamic Menu Cell Updating

[jordynmackool]

Hello SDL community,

The review of "SDL 0210 - Mobile Manager Dynamic Menu Cell Updating" begins now and runs through December 11, 2018. The proposal is available here:

https://github.com/smartdevicelink/sdl_evolution/blob/master/proposals/0210-mobile-dynamic-menu-cell-updating.md

Reviews are an important part of the SDL evolution process. All reviews should be sent to the associated Github issue at:

#637

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of SDL. When writing your review, here are some questions you might want to answer in your review:

• Is the problem being addressed significant enough to warrant a change to SDL?
• Does this proposal fit well with the feel and direction of SDL?
• If you have used competitors with a similar feature, how do you feel that this proposal compares to those?
• How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
  Please state explicitly whether you believe that the proposal should be accepted into SDL.

More information about the SDL evolution process is available at

https://github.com/smartdevicelink/sdl_evolution/blob/master/process.md

Thank you,
Jordyn Mackool

Program Manager - Livio
jordyn@livio.io

[kshala-ford]

Though I like optimizations I'm afraid reordering will not work as proposed. the concern is specific to your example 4 applying your algorithm to it:

• Step 1 of your algorithm is simple and straight forward. All items of the old list are marked for deletion.
• Step 2... this should already fail because there are no commands in the same order comparing both lists. Details:
  • ABCD vs BADC. The new list does not contain AB, BC or CD, So there's no order identified

I do understand the benefits for simple additions or removals at the end of the list but I don't think the algorithm is accurate. Could you please provide more details to the algorithm? I believe the algorithm is far more complicated as you might expect and without understanding the details we will be trapped when realizing this proposal.

[joeljfischer]

Hey Kujtim, between the lists ABCD and BADC, A and D are in the same order. So if deleteCommands are sent for B and C, the new menu will be AD. When an AddCommand for B is sent with position 0 and an AddCommand for C is sent with position 3, the menu list will become BADC. Does that follow?

The commands don't have to be next to each other in order for them to be marked as remaining. So when looping through the list. A is the first item in list 1. When it is found in list 2, it is unmarked. B is then checked. It is found in list 2, but before A, therefore it remains marked for deletion and addition.

Now, this algorithm performs poorly if, for example, we change the list from ABCD to BCDA. Ideally, you would only have to delete and add one item. However, because of how the algorithm works, you have to change 3 items. Any suggestions on improvement on this point are welcome.

[kshala-ford]

As a human I already understand your approach. What I'm saying is that the algorithm steps are very unclear and vague but your comment helped. So for ABCD -> BADC A and C remain while B and D are deleted (as you wrote in your proposal doc). Also the algorithm has to be recursive for sub menus?

Regarding the algorithm I believe you want to reach O(nlogn) but your comment would be O(n^2). While iterating the old list the algorithm should remember the item and index in the new list so that the algorithm could skip items in the new list for the next iteration.

1. Search for A from ABCD in BADC starting at index 0.
   • B at index 0. B can be finally marked as addition at position 0
   • A was found at index 1. You can remember that A was found at index 1 and break;
2. Next search for B starting at index 2. There's no need to start at index 0.
   • B was not found in (BA)DC (Alternatively we could skip B because B is already marked as finally addition at position 0)

and so on. Above steps would provide O(nlogn) as you skip items you already checked and also mark items to be added with the known position.

Regarding the poor performance to change ABCD to BCDA. Any change of multiple Commands (especially with voice recognition) can be a nightmare. Delete commands are no issues but adding them requires computational time for voice grammars. It's even worse if sub menus. Imagine B, C and D to be sub menus with >1 sub command...

This worse case can be improved by running the algorithm multiple times and add scores to each run. Every run is with a subset of the old list. Here's an example (no submenus):

1. Run: ABCD <> BCDA Score is 3 additions. 3 deletions.
2. Run: BCD <> BCDA Score is 1 addition. 1 deletion (A is skipped and marked for deletion).
3. Run: CD <> BCDA Score is 2 additions. 2 deletions (AB are skipped and marked for deletion).
4. Run: D <> BCDA Score is 3 additions. 3 deletions (ABC are skipped and marked for deletion).

Run#2 would win with only 1 addition.

For commands the score is 1. For submenus the score is numOfSubCommands + 1. So if A is a submenu with 10 commands the scores would show that Run#1 is best (3 additions vs Run#2 11 additions).

You might think that's more complicated than needed but you need to consider the time needed to compute the voice grammars. Every intelligent algorithm to reduce number of RPCs is beneficial when voice is related.

[jordynmackool]

The Steering Committee voted to defer this proposal on 2018-12-11 to allow the author time to respond to this comment.

[joeljfischer]

I apologize, if I misrepresented the algorithm here by saying that B is found in list 2; I meant that it exists in list 2 before A, not that that algorithm finds it before A. That was confusing. If A is found in slot 2 according to my above comments (of BADC), then B would begin searching in slot 3 through to the end, and would not find it. Hence the O(n*log(n)) as you noted above (for equivalent length source and target lists). Regarding running the algorithm multiple times, would that not increase the size of our algorithm to O((n*log(n))^2)? That concerns me a bit for larger sized menus, but since we're capped at 100, shouldn't be too bad?

I'm going to keep thinking on this.

[kshala-ford]

The increased complexity by running the algorithm multiple times is true. However computational time is still very very low (I assume < 1ms for 100 items worse case but should be confirmed). Compare that with an AddCommand request especially with voice. The roundtrip time to send each request can be considered > 1ms. Creating voice grammars can take up to 1 second per VR command.

Every intelligent idea to reduce the number of RPCs is worth being considered.

[joeljfischer]

Some point of clarification before the meeting:

1. We should implement @kshala-ford's idea to reduce the number of RPCs needed to its minimum (assuming performance tests turn out okay).

2. When adding menu items using position, we can run into some sticky situations if we don't use sequential RPCs (wait for the response before the next request is sent). For example:

If we had A,B,C,D,E -> C,B,D,A,E then C,D,E would stay, while we would add B at position 1 and A at position 3 (0 based). If A(3) got added before B(1), then there would be a problem and the resulting menu would be C,B,D,E,A, which is incorrect.

[jordynmackool]

The Steering Committee voted to accept this proposal with revisions on 2018-12-19. The author is to updated the proposal to include the two points called out in this comment.

[jordynmackool]

The accepted revisions were made on 2019-01-03, issues have been entered:
iOS
Android