Jul 25, 2016

The Way of the Lambda - Elegant and Efficient

In Java 8, you can do
items.removeIf(i -> predicate(i));
where you used to do
for (Iterator it = items.iterator(); it.hasNext();) {  
    if (predicate(it.next())) {
        it.remove();    
    }
}
which is not only considerably more elegant but also a more efficient solution in some cases. I have the graphs to prove it!

Background

Recently having spent a few years away from Java development, it is great to be back and find that Java 8 indeed has delivered on what was promised in 2013. With lambdas and streams it is possible to tackle problems in a functional manner and write code that is both readable and efficient. This over due modernization of the language is by far the most important change in Java 8, but there are also other improvements that deserve mentioning. This post elaborates on the topic of Collection.removeIf() which allows for conditional removal of elements of a collection.

The Way of the Iterator

Removing elements of a collection while iterating over it is somewhat like cutting off the branch on which you are sitting, but by using Iterators that can be done without a runtime ConcurrentModificationException. Consider the following typical simplistic example, where the elements of the collection items for which predicate() holds true are removed.
for (Iterator it = items.iterator(); it.hasNext();) {
    if (predicate(it.next())) {
        it.remove();    
    }
}
If the collection in question is a linked list of size n and m elements are removed, the full iteration with removals is O(n + m) = O(n) since iteration steps and removal from the list are constant time operations and m is limited by n. If, however, the data structure of the collection is one where removal is relatively expensive compared to iteration, the complexity becomes less favorable. For an ArrayList a single removal step is O(n) since all items at higher indices have to be moved. There are still n iteration steps to be made so the full sequence of removals becomes O(m*n) which is O(n^2) assuming worst case with the number of removals being a constant fraction of the array size.

In more pragmatic terms, what happens in the ArrayList case is that for each element that is removed, all elements of higher indices are moved to fill the gap in the backing array. This is clearly suboptimal since that operation is repeated for each removal. Thus, to reach its final destination an element will visit all locations between the starting position and the destination. In case many elements are removed, this may be a considerable amount of work in vain.

The Java 8 way of the lambda

In Java 8, the code snippet from above can be expressed as follows.
items.removeIf(i -> predicate(i));
Clearly more concise, this expression is also more efficient on an ArrayList compared to the Iterator approach. Where the Iterator requires completion of each removal operation before continuing to the next one, removeIf operates on a predicate and can therefore iterate over all items once to determine which elements are to be removed and then shift the remaining elements to the correct new indices all in a second pass. Therefore, removeIf is O(n) since it performs two linear passes through the collection.
Each retained element in the resulting collection is moved just once, while for the Iterator approach it would be moved one step at a time towards its destination. See this gist for the relevant JDK code.

The Difference Visualized

We compare execution times for the two approaches as a function of the array size for a rather extreme case where 999 out of 1000 items are removed from an ArrayList. For each data point 40 runs are made, the 5 fastest and slowest outliers are removed and the sum of the remaining 30 form the execution time value. For details please refer to this gist.

We expect the execution time to be considerably shorter for the Java 8 way of the lambda and as a matter of fact that is what we find. We also note that within the resolution of the graph, the lines are quite noise free due to the many repeats and filtering of outlier results.



For array sizes of 150,000 elements, the removeIf() approach is more than 3000 times faster. Even more importantly, the factor between the two increases as the size of the array increases which is expected since the way of the lambda has a superior asymptotical time complexity.

To better compare the time complexity of the two, we scale up the green line to match the green one. By multiplying the execution times of the faster algorithm by ~1500, the graphs can be compared in terms of shape. As expected, we find linear behavior for the Java 8 removeIf() design, while the old ways show a quadratic time complexity due to the inefficient removal of elements.


When scaling up the measurements we get to see some noise in the green line. The sensitivity to random fluctuations in execution time is greater since the execution times are several orders of magnitude shorter compared to the blue. Both lines are fitted to polynomials of power two and as can be clearly seen, the light green line is very similar to a straight line while the blue line clearly aims for the sky in a super linear fashion.

Edit: There is a reddit thread about this blog post. Good points are being made there, for example the fact that the removeIf implementation is atomic (in the database sense) as it first evaluates the predicate for all items before making any alterations to the list. Thus, if the predicate throws an exception for any of the items in the list, the list will remain unchanged.

Also published at DZone: The Way of the Lambda and removeIf().


27 comments:

  1. How does it compare with an index loop?
    for (int i = 0; i < arrayList.size(); i++) {
    if (condition) arrayList.remove(i--);
    }

    ReplyDelete
    Replies
    1. That is also O(n^2). The loop will pass n times, and each remove operation is O(n), so we end up with an O(n*n) solution.

      Delete
    2. The cost to remove a item from a Collection depends on the implementation.
      The most famous being Arraylist O(N) and LinkedList O(1)

      Delete
    3. Initialize your i to the arrayList.size()-1 and decrement. That will be faster.

      Delete
    4. Backwards is faster but still O(n^2). I agree that the cost of removal is highly dependent on the data structure used. Contrasting with a LinkedList in the beginning, this blog post is intended to cover only the special case of an ArrayList.

      Delete
  2. Your solutions also works in O(n^2) time - after each removal all elements in ArrayList will be shifted in memory.
    One of the easiest solutions without Java Streams is to create new list only with elements satisfying predicate:

    List filteredItems = new ArrayList<>();
    for (Item item: items) {
    if (predicate(item)) {
    filteredItems.add(item);
    }
    }

    ReplyDelete
    Replies
    1. I did not intend to convey that I have created any novel solution to the removal problem, on the contrary I meant to point out that the Java 8 remove operation is O(n). Thus, none of the solutions are mine in any sense.

      I think that your comment beautifully illustrates the reason why the The Java 8 implementation is more efficient. Ignoring any language or implementation details and just considering the problem per se, it is easy to see that removal of elements in an array is O(n) (since it entails relocation of O(n) elements). Thus, solving the general problem of removing n elements from an array by using the basic removal operation will always be O(n^2).

      The reason for this is that we have introduced an extra constraint to the original problem when deciding to use item removal operations. The basic item removal operation has to maintain the data structure invariants for each loop of our solution, which (as you point out) requires relocation of all elements of higher indices.

      Your suggestion demonstrates a straight-forward solution to the problem - just copy the data over to a new structure while figuring out the new position of the element. The Java 8 removeIf solution is slightly more complex but avoids creating a new List. (Basically two passes - one to find the elements to move and a second to move each element once to its new position.)

      See https://gist.github.com/lawesson/101ed054fcdb00a94d69b34e04ef0be7

      Delete
  3. Does the Java 8 solution silently use multithreading ?
    Or can it be modifier for this ?

    ReplyDelete
    Replies
    1. As written above, the execution will take place in a single thread. It is how ever trivial to add a ".parallel()" to the stream to make the solution using several threads. When happens then is that the stream is split into chunks of data, to be handled in parallel streams created transparently to the user.

      Good question, BTW, in some future blog post I will use this as an example of the advantages of declarative programming.

      Delete
  4. This comment has been removed by a blog administrator.

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Admiring the time and effort you put into your blog and detailed information you offer!..
    Lyko Rabattkod

    ReplyDelete
  7. I recently came across your blog and have been reading along. I thought I would leave my first comment. I don’t know what to say except that I have enjoyed reading. Nice blog, I will keep visiting this blog very often. melodifestivalen odds

    ReplyDelete
  8. Hi was just seeing if you minded a comment. i like your website and the thme you picked is super. I will be back. BODYCONTACT

    ReplyDelete
  9. I am very enjoyed for this blog. Its an informative topic. It help me very much to solve some problems. Its opportunity are so fantastic and working style so speedy. Posters

    ReplyDelete
  10. Really a great addition. I have read this marvelous post. Thanks for sharing information about it. I really like that. Thanks so lot for your convene. bet9ja mobile

    ReplyDelete
  11. I went over this website and I believe you have a lot of wonderful information, saved to my bookmarks Visit Cyprus

    ReplyDelete
  12. Nice post. I was checking constantly this blog and I’m impressed! Extremely useful info specially the last part I care for such information a lot. I was seeking this certain info for a long time. Thank you and good luck. villa for sale los arqueros

    ReplyDelete
  13. Sale and Rent on the Costa del Sol, such as: Luxury VILLAS FOR SALE IN LA ZAGALETA SpainForSale.Properties is considered one of the most trusted Exclusive Real Estate Agencies in Marbella, Costa del Sol and other “Prime Locations” in Spain.Nestled in the rolling green hills of Los Flamingos is this exceptional state-of-the-art villa which is built to the highest specification of luxury, and enjoys some of the very best views across the Mediterranean Sea, and to Gibraltar and the coast of North Africa. Famed as the home to the 5 Star Hotel Villa Padierna, the area is synonymous with the exclusive lifestyle that so many seek in the Costa del Sol. and this stunning villa is a true reflection of this. Designed and fitted with the latest technology, the property is built with practicality, comfort and security as the priority. No expense has been spared with the materials and fixtures that have been used and this is evident from the very first step into this Los Flamingos villa. French doors opening to a private porch and garden with swimming pool with beautiful views to the surrounding scenery. En-suite master bedroom on the upper level, also with beamed high ceilings, has a dressing area and small balcony with panoramic sea views. Along with the highly specified designer appliances in the kitchen and all of the bathrooms, there is also a superb cinema room boasting the optimum technology in surround sound and visualisaton. The layout has been configured to ensure that each and every room benefits from delightful views of the surrounding Los Flamingos countryside, and ultimately from the wonderful roof terrace upon which there is a lovely jacuzzi from which the scenery is truly impressive.

    Stunning, fully renovated villa, located in the heart of the Golf Valley in Las Brisas, Nueva Andalucía.

    ReplyDelete
  14. A 10 min drive brings you to the famous Puerto Banus and a little further into Marbella and the Malaga airport is about a 50 min drive away.
    Apartments for sale in Marbella, Spain.
    Properties for sale Marbella, Spain.
    Apartment for rent in Marbella, Spain.
    Guests will have full use of the resident’s gym facility, swimming pool with sun beds. Which during the popular summer months is monitored by a lifeguard. The stunning gardens are well maintained, and lit by night lanterns. There is a security coded gate at the rear of the development which leads residents straight to the beach via a half a minute walk along a path.
    The Las Terrazas development is gated from the public offering privacy and seclusion, and has the advantage of a garage car parking space for one car and a security guard on duty at the entrance to the development over the evening and night.
    Apartments for sale in Marbella, Spain.
    Properties for sale Marbella, Spain.
    Apartment for rent in Marbella, Spain.
    Spacious 3 bedroom and 3 bathroom south facing duplex penthouse in the very popular frontline beach complex Alcazaba Beach close to Estepona (walking distance). With views to the gardens and direct access to the beach. On the main floor you have the living and dining area with direct access to the main terrace, fully fitted kitchen, two guest bedrooms, one en suite and one separate bathroom. The upper floor offers the master bedroom en suite with dressing area, a large terraces with bbq area. There are 2 garage spaces and one storage room. Several Community pools (one heated), lush mature gardens, 24 hrs security, tennis court, fitness area. 193 m2 living area plus 209 m2 terraces. Price: 750.000,00 €.
    Image may contain: sky, pool, tree, outdoor and nature
    Apartments for sale in Marbella, Spain.
    Properties for sale Marbella, Spain.
    Apartment for rent in Marbella, Spain.
    3 Bedroom Duplex Penthouse in Pueblo Bermejo
    Marbella Golden Mile
    Lovely 3 bedroom Duplex penthouse property for sale in a great location right in the centre of Marbella's Golden Mile. Ideal family home.
    The apartment is located in the well-kept development Pueblo Bermejo in the hills across from the Marbella Club Hotel and within easy reach of all amenities.
    Sale and Rent on the Costa del Sol, such as: Luxury VILLAS FOR SALE IN EL MADRONAL SpainForSale.Properties is considered one of the most trusted Exclusive Real Estate Agencies in Marbella, Costa del Sol and other “Prime Locations” in Spain.

    ReplyDelete
  15. Apartments for sale in Marbella, Spain.
    Properties for sale Marbella, Spain.
    Apartment for rent in Marbella, Spain.
    FRONTLINE BEACH, duplex penthouse in immaculate condition offering panoramic sea views in Elviria (Marbella East)! The property forms part of the well-known White Pearl Beach II-complex. It is very rare to find a penthouse for sale in this complex, so here is your chance to purchase a lifestyle property under the sun.

    LAYOUT: Entry level comprises the entrance with cloakroom for guests, a fully equipped kitchen with separate utility room, a bright and cosy living & dining room with amazing sea views and access to an ample open terrace with awnings. On this level is also the master bedroom suite. Upstairs are further 2 bedrooms en-suite. The bathrooms on this level are newly fitted with under floor heating.
    SPECS include built-in wardrobes, double glazing, electric blinds in bedrooms, marble floors. Included in the price is a parking space and a storeroom in the underground garage.
    The complex is fully gated and has 2 smaller pool areas and is situated by the sandy dunes and the best beaches on the entire Costa del Sol, hence the huge all-year-around rental potential. Walking distance to all services.

    Elviria is home to world-famous Nikki Beach, 5-star Hotel Estrella del Mar with beach club, 5-star Hotel Don Carlos with tennis club, 2 golf courses, public- & international schools. Elviria is the main centre in Marbella East and offers all in services and facilities.
    Apartments for sale in Marbella, Spain.
    Properties for sale Marbella, Spain.
    Apartment for rent in Marbella, Spain.
    This apartment offers many extras, and is finished to the highest of specifications throughout. The stunning complex has an outdoor gym and a beautiful pool area, all located next to a prestigious golf course. The high class finishes in the apartment are by Porcelanosa and there is hot and cold air conditioning throughout. There are brand new fitted appliances including washing machine, dryer, dishwasher, oven, microwave and fridge/freezer. Both bedrooms have electric curtains and the whole apartment is tastefully furnished. The private underground garage has space for 2 cars, and there is also a large storeroom on this level. The complex is securely located within a gated community, and is only 700 metres away from Mercadona. Located halfway between Marbella and Estepona, in the heart of Atalaya Alta. This development finds itself in one of the most exclusive settings, surrounded by nature and just steps from all sorts of amenities, services, restaurants, beaches, golf courses and schools, etc. Sale and Rent on the Costa del Sol, such as: Luxury VILLAS FOR SALE IN MARBELLA SpainForSale.Properties is considered one of the most trusted Exclusive Real Estate Agencies in Marbella, Costa del Sol and other “Prime Locations” in Spain.
    Apartments for sale in Marbella, Spain.
    Properties for sale Marbella, Spain.

    ReplyDelete
  16. Famed as the home to the 5 Star Hotel Villa Padierna, the area is synonymous with the exclusive lifestyle that so many seek in the Costa del Sol. and this stunning villa is a true reflection of this. Designed and fitted with the latest technology, the property is built with practicality, comfort and security as the priority. No expense has been spared with the materials and fixtures that have been used and this is evident from the very first step into this Los Flamingos villa. French doors opening to a private porch and garden with swimming pool with beautiful views to the surrounding scenery. En-suite master bedroom on the upper level, also with beamed high ceilings, has a dressing area and small balcony with panoramic sea views. Along with the highly specified designer appliances in the kitchen and all of the bathrooms, there is also a superb cinema room boasting the optimum technology in surround sound and visualisaton. The layout has been configured to ensure that each and every room benefits from delightful views of the surrounding Los Flamingos countryside, and ultimately from the wonderful roof terrace upon which there is a lovely jacuzzi from which the scenery is truly impressive.

    Stunning, fully renovated villa, located in the heart of the Golf Valley in Las Brisas, Nueva Andalucía. The property is distributed over three levels, and comprises, on entrance level: entrance hall; spacious living-dining room with fireplace and access to the partially covered terrace, saline heated swimming pool, pool bar with BBQ, and garden space; open-plan fully fitted kitchen with top quality Bosch appliances and breakfast area with stools; two guest bedrooms, both with access to the terrace & sharing a bathroom; further guest toilet. Sale and Rent on the Costa del Sol, such as: Luxury APARTMENTS FOR SALE MARBELLA SpainForSale.Properties is considered one of the most trusted Exclusive Real Estate Agencies in Marbella, Costa del Sol and other “Prime Locations” in Spain.

    ReplyDelete
  17. On the upper level: en-suite master bedroom with dressing area; guest en-suite bedroom with staircase leading to the rooftop solarium; second guest en-suite bedroom. All three bedrooms have access to a large terrace with panoramic sea views towards Gibraltar and North Africa. There is a guest apartment at the entrance level with en-suite bedroom and cozy terrace and also a double garage. Beautiful mature garden with sea and mountain views, salt water heated pool and a barbecue area for "al fresco" dining. Other features include: air conditioning, automatic irrigation system, alarm. A very private family home, in a tranquil area, only within a 15-minute drive to Puerto Banús. In addition, there are 7,590 m2 of extra land (qualified as a green zone) surrounding the main plot, and which also belong to the property.

    Beautiful Townhouse ready to move into now! This delightful townhouse with 4 bedrooms and 3 bathrooms, is situated in Las Brisas del Sur in Nueva Andalucía, and is available for Long Term Rental at a cost of €1,800 per month. On the entry level, there is the sitting room area with fireplace leading out to a spacious terrace, a fully fitted kitchen with breakfast bar, a good sized bathroom, and a large double bedroom, also giving access to the terrace. On the upper level is the master bedroom suite with it's own spacious private terrace, wardrobes offering generous storage space, and a large bathroom. On the lower level, there are 2 more spacious bedrooms, a bathroom, a large utility room, and a door giving access to the private garage. The complex offers a communal swimming pool and a putting green for the use of residents.Sale and Rent on the Costa del Sol, such as: Luxury VILLAS FOR SALE IN LA ZAGALETA SpainForSale.Properties is considered one of the most trusted Exclusive Real Estate Agencies in Marbella, Costa del Sol and other “Prime Locations” in Spain.

    The villa in Santa Mª Golf Elviria is located in a privileged location in an ideal setting with all the amenities nearby.

    ReplyDelete
  18. Luxury Properties (Apartments, Villas,..) for sale in Marbella, Spain.
    Luxury Villas for sale in Marbella, Spain.
    We would like to remind you of this south facing outstanding villa, located in Marbella Hill Club and exclusive to spainProperties. Due to its elevated position the property offers great views of the sea. The property has a total built area of 1.278 sqm. on a 4.795 sqm. plot and is distributed over three levels, offering 6 bedrooms and 6 bathrooms. Luminous and spacious, the house is built with great quality construction throughout. Close to Marbella, Puerto Banús, golf courses and all the other amenities of this area, the villa is set between sea and mountains, offering not only commanding views but also a sense of peace and privacy close to nature trails at the edge of a protected reserve. This well-presented property is offered with a garage for two cars and a generously sized drive.
    Marbella, villas for sale.
    Luxury Villas for sale in Marbella, Spain.
    Stunning mansion with fabulous sea & golf views in Reserva de La Quinta
    6.500.000 Euros
    Property image main
    Left property image Centre property image Right property image
    11 Bedrooms - 11 Bathrooms
    1.718 m2 built - 304 m2 terraces - 5.375 m2 plot
    Marbella, villas for sale.
    Luxury Villas for sale in Marbella, Spain.
    Remarkable frontline golf hilltop mansion in a gated complex in La Quinta, enjoying superb sea and golf views, and with beautiful landscaped tropical gardens with pool and BBQ area.
    Built with top qualities throughout. A courtyard with fountains leads to the main entrance. Distributed over four levels, it comprises, on main floor: hall; guest toilet and cloakroom; living room with fireplace and access to the porch also with fireplace; formal dining room; library with fireplace; rustic-style kitchen with independent entrance and patio; en-suite bedroom with walk-in wardrobe; further en-suite bedroom off the kitchen for staff.
    Upstairs: gallery; en-suite master bedroom with fireplace, "his and hers" walk-in wardrobes and terrace with sea views; 3 further en-suite bedrooms. Basement level: temperature controlled wine cellar with bar; store room; laundry room with interior patio; tool room.
    On an even lower level, an impressive gym with indoor heated pool, sauna, changing and shower rooms. 3 independent apartments: one with 1 en-suite bedroom, another with 2 en-suite bedrooms with walk-in wardrobes and staff´s apartment with 2 bedrooms. Garage for 3 cars. Gardener's room with bathroom.
    A unique residence with outstanding views!
    Luxury Properties for sale in Marbella, Spain.Sale and Rent on the Costa del Sol, such as: Luxury PLOTS FOR SALE MARBELLA SpainForSale.Properties is considered one of the most trusted Exclusive Real Estate Agencies in Marbella, Costa del Sol and other “Prime Locations” in Spain.

    ReplyDelete
  19. This was really an interesting topic and I kinda agree with what you have mentioned here! värmeväxlare

    ReplyDelete