J'ai une liste / flux de java 8 Comment puis-je découvrir rapidement Subliste de celui qui se trouve dans une période donnée 12 heures Si l'horodatage de démarrage est Le subliste d'horodatage doit être après le début et avant la fin. < / p> localDateTime (horodatage) qui est dans l'ordre ascendant (chronologique). 2019-03-01T10: 10: 10 < / code>, alors l'horodatage final est 2019-03-01t22: 22: 21
3 Réponses :
Vous pouvez essayer de rechercher les deux extrémités de la liste, de compter des indices jusqu'à ce que vous trouviez le premier index après ou égal à l'heure de début souhaitée, tout en itérant à l'arrière pour obtenir l'index de la dernière fois dans la période que vous recherchez. .
Quelque chose comme: Le sous-ensemble que vous rechercherez sera alors tout entre ces indices (inclus)
C'est toujours une opération O (n) qui boucle la majeure partie de la liste.
La complexité du temps est toujours n et donc pas plus rapide que d'itération sur tous les éléments.
La question demande une méthode qui atteint son objectif: "Sans boucle pour tous les éléments de la liste" Vous devriez peut-être lire la question ?. Étant donné que la question ne précise pas si tous les horodatages sont à intervalles réguliers, l'hypothèse qu'elles sont distribuées de manière uniforme n'est pas valable.
Eh bien, combien de la liste votre solution sera-t-elle votre solution si la plage de temps donnée n'est pas dans la liste?
À quelle vitesse pourriez-vous vérifier le premier élément pour vous assurer qu'il est?
Dans une liste ordonnée et aléatoire, dans Of (log (n)) heure.
Eh bien, en fait, vous pouvez vérifier les premier et les derniers éléments de O (1) heure - étant donné qu'il est spécifié en tant que liste.
Et si vous ne vérifiez pas que le premier élément est avant votre valeur de fin de la plage et, le dernier élément correspond à votre valeur de départ avant de faire autre chose, vous devriez vraiment.
Vous pouvez utiliser Sous-ensemble Méthode de Sous-ensemble NAVIGABALET (EMENTEMENT EMENT,
booléen fromnclusive,
E toelement,
booléen toclive)
Cela pourrait être comme ceci: NAVIGABALET
Je peux vous proposer le code suivant qui n'utilise pas la chute du tout:
import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Arrays;
import java.util.List;
import java.util.function.BiPredicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SublistWithLambda {
public static void main(String[] args) {
List<LocalDateTime> dates = Arrays.asList(
LocalDateTime.now().minusHours(24),
LocalDateTime.now().minusHours(22),
LocalDateTime.now().minusHours(20),
LocalDateTime.now().minusHours(12),
LocalDateTime.now().minusHours(10),
LocalDateTime.now().minusHours(7),
LocalDateTime.now().minusHours(5)
);
BiPredicate<LocalDateTime, LocalDateTime> isLessThan12Hours = (date1, date2) -> {
Duration duration = Duration.between(date2, date1);
return duration.toHours() >= 0 && duration.toHours() <= 12;
};
List<List<LocalDateTime>> result = IntStream
.range(0, dates.size())
.mapToObj(i -> dates.stream().skip(i)
.takeWhile(date -> isLessThan12Hours.test(date, dates.get(i)))
.collect(Collectors.toList()))
.collect(Collectors.toList());
result.forEach(System.out::println);
}
}
Si vous utilisez des flux, toute recherche doit être linéaire. Si la liste est basée sur une matrice, vous pouvez utiliser les fonctions de recherche binaires dans les tableaux
.S'ils sont en ordre croissant d'ordre chronologique, vous pouvez quitter la boucle lorsque vous rencontrez le premier horodatage> = début horodatage. Ensuite, vous pouvez faire la même chose en boucle dans l'ordre inverse.
Si vous utilisiez Java 9+ et que vous aviez besoin / que vous vouliez utiliser des flux, je dirais utiliser
flux.dropwhile (prédicat)en combinaison avecflux.takewhile (prédicat).Si la liste
est une liste et triés, vous pouvez trouver le plus petit élément plus grand questarttime et le plus gros élément inférieur àde l'extrémité/ code> dansjournal (n) . Ainsi, la recherche ne prend quejournal (n) , oùn est la taille de la liste. Sans plus d'informations, toutefois, aucune estimation supplémentaire de l'opération de copie ne peut être faite et doit ainsi être estimée avec complexitén .@Realskeptic Il y a aussi
collections.binaireSearch (liste, objet).@Slaw " Cette méthode fonctionne dans le temps de journal (n) de la liste" Accès aléatoire "(qui fournit un accès positionnel de temps presque constant). Si la liste spécifiée ne met pas en œuvre le
randomAccess Interface et est grand, cette méthode fera une recherche binaire basée sur itératrice qui effectue des trersons de liaison O (n) liaison et des comparaisons d'éléments O (log n). "@Slaw OUI, le même principe - la liste doit être un accès aléatoire (qui signifie généralement, basé sur une matrice).
@Realskeptic a accepté. Je pensais juste que je le mentionnerais comme votre commentaire pourrait être interprété comme indiquant que seuls les tableaux fournissent une telle fonctionnalité, ce qui nécessiterait de convertir la liste en une matrice.
@ Turing85 Je ne suis pas sûr de comprendre pourquoi vous avez cité cela à moi (je suis lié à la documentation)?
@Slaw parce que cela ressemblait à ce que vous vouliez impliquer que
binaireSearch (...) "fonctionne plus vite" queo (n) qui est, w.l.o.g., pas le cas.@Slaw J'aime le
DÉCLARWHILE etMAINTIEN MAIS UNE APPROCHE . Merci.@ttt qui ne vous donnera rien de mieux que O (n), du moins pas en fonction de la documentation des méthodes.
Comme Realskeptic déjà mentionné, ces méthodes seront toujours linéaires et dans le pire des cas "en boucle" sur tous les éléments; Cependant, il "briser" de la "boucle" tôt si possible. Je vous recommanderais de les utiliser que si vous êtes bloqué à l'aide d'un flux .